1
$\begingroup$

Assume we want a divide-and-conquer algorithm that finds the max and min of a set $S$ with $n = 2^k$ elements, e.g. mergesort. The recurrence for time complexity is

$T(n)=2*T(n/2) +2$, for $n>2$, and $T(2)=1$

Using domain transformation we can set $n=2^k$, then $T(n)=a_k=T(2^k)$

Since $2^k/2=2^{k-1}=a_{k-1}$,

$a_k = 3/2*2^k-2$

Solving this gives us $T(n)=3/2*n-2$, which is clearly $O(n)$

But, from the master theorem, $T(n)$ is in the form $aT(n/c)+bn$, and $a=c=2$, so we should be getting $n\log{n}$. This is also what most online sources say is the time complexity of mergesort. Why can't I get $n\log{n}$ as solution?

$\endgroup$
4
  • $\begingroup$ How are you merging two lists of arbitrary size with just two operations? $\endgroup$
    – Deedlit
    Commented Apr 13, 2015 at 5:03
  • $\begingroup$ In the ideal case you have the pointers to the start and end of each array, and they are sequential, and all you have to do is specify the start pointer of one array and the end pointer of another. $\endgroup$
    – Whitesizzle
    Commented Apr 13, 2015 at 7:54
  • $\begingroup$ So are you assuming that that the numbers are already in the correct order to start with? Keep in mind that O(n log n) represents the time for the worst case, not the best case. $\endgroup$
    – Deedlit
    Commented Apr 13, 2015 at 11:25
  • $\begingroup$ Not necessarily pre-sorted items but it works in the case where one list is wholly larger than another list. I'll agree it doesn't have any practical use but I wanted to make a=c. $\endgroup$
    – Whitesizzle
    Commented Apr 13, 2015 at 13:59

1 Answer 1

Reset to default
3
$\begingroup$

You are confusing several different things:

  1. Mergesort is a sorting algorithm. Not every divide-and-conquer algorithm is mergesort.

  2. If you apply the master theorem then you get $\Theta(n)$, since your recurrence is not of the form $T(n) = aT(n/c) + bn$ but rather of the form $T(n) = aT(n/c) + b$.

  3. Your recurrence only measures the number of comparisons, so in this case this is fine, since the running time is proportional to the number of comparisons (for this algorithm).

$\endgroup$
3
  • $\begingroup$ I think I get it. So for mergesort, the sorting is actually $O(n)$, but since you need to merge the lists, which generally takes $bn$ operations, the whole algorithm is $O(n\log{n})$. How did you determine that $T(n) = aT(n/c)+b$ would be $O(n)$? Is there a version of the master theorem without $b$? $\endgroup$
    – Whitesizzle
    Commented Apr 13, 2015 at 8:02
  • $\begingroup$ I used the standard version of the Master theorem. Take a look at the Wikipedia page on the Master theorem. $\endgroup$
    – Yuval Filmus
    Commented Apr 13, 2015 at 14:29
  • $\begingroup$ Ok got it. $f(n)$ is constant = $O(1)$ in this case. $c<log_ba$ $(c=0, a=2, b=2)$, so the result is $O(n)$. $\endgroup$
    – Whitesizzle
    Commented Apr 13, 2015 at 15:46

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .