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$