Compare two complexity functions having the same asymptotic complexity

Question

For a certain problem two solution algorithms (A1 and A2) with the following execution times have been found:

• $A1: T_{A1}(n)=4n^2 +7log(n^2)$
• $A2: T_{A2}(n) = 4T(n/2) + log(n)$

Say, technically justifying the answer, which of the two algorithms is preferable for input of size sufficiently large

Here my solution

For $A1$ there is no recursion, the predominant term is $4n^2$ so we can say:

Complexity of $A1 = O(n^2)$

For $A2$ we do have recursion, Let's use the Master Theorem:

$a = 4$, $b = 2$ and $f(n) = log(n)$

$$f(n) < n^{\log_{b} a}$$ $$log(n) < n^{\log_{2} 4}$$ $$log(n) < n^2$$

Hence, $T_{A2}(n) = \theta(n^2)$

Here comes my question: Which one is preferable and why ?

I'd say there is no difference since both algorithms have an upper bound of $c\cdot n^2$

Answer 1

Although, you cannot find the arbitrary constant c from master theorem, you should check using different size inputs which algorithm is faster, because even though both are upper bounded by c*n^2, if we have 4*n^2 and 1/4*n^2, still 1/4*n^2 is 16 times faster !!

A very important point is that your second algorithm seems to use divide and conquer method. This means that maybe it can be parallelized (in order to use more space but less computing time). For example, assuming an ideal choice of pivots, parallel quicksort sorts an array of size n in O(n log n) work in O(log² n) time using O(n) additional space.