3
$\begingroup$

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$

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Is it correct to say that the two algorithms have the same asymptotic complexity? Is my solution correct? $\endgroup$ – ddon-90 Jan 21 at 10:11
  • 1
    $\begingroup$ Yes it is correct to say that the two algorithms have the same asymptotic complexity. The first algorithm is obviously O(n^2). For the second algorithm you can also use wolfram alpha link to see the complexity (instead of Master Theorem). BUT ! Having two algorithms of the same asymptotic complexity doesn't mean that they are equally preferable (specially in real life problems) as I explained in my answer. $\endgroup$ – entropyfeverone Jan 22 at 16:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.