0

I was hoping to get some clarification on something...

I'm learning about recurrence relations, and one that I'm trying to do as an example is mergesort. I've done the recurrence relation several times and the result I keep getting is O(N), even though the textbook says it's O(Log(N)).

Mergesort has the recurrence :

T(1) = 1 T(N) = 2 * T(N/2) + c

After a few iterations I get...

2^k * T(N/2^k) + C*sum(i = 0 -> k-1)2^i

When I solve for k, I get log2(N), so I can simplify in the following way:

(2^log2(N)) * T(N/2^log2(n)) + C*sum(i = 0 -> k - log2(n)-1)2^i =

N * T(N/N) + C(N-1) = N * d + CN + N

Which boils down to O(N)

HOWEVER

According to my textbook, Mergesort should be O(log(N)).

Is there something wrong with my calculations?

I also found someone did the same relation here and got the exact same result : http://courses.cs.washington.edu/courses/cse326/06su/lectures/lecture13_proofs.pdf

Any guidance would be appreciated!

SemperCallide
  • 1,950
  • 6
  • 26
  • 42

2 Answers2

3

The time complexity of merge sort is neither O(N) nor O(logN), but O(NlogN) instead.

See this figure:

enter image description here

For each layer, you have to check every of the N elements to put it to the right place. it takes O(N).

And you have logN layers. So the overall complexity is O(NlogN).

Timothy
  • 4,467
  • 5
  • 28
  • 51
2

Your recurrence is a bit off. What your recurrence (and the link you posted) describes is the case where you can check that the two subarrays you're supposed to merge are already properly ordered, in which case you do get O(N) since the merge step is constant time (you don't do anything).

The correct mergesort recurrence is:

T(N) = 2 * T(N / 2) + N

where the last N factor comes from the merge step which is linear time.

Try with this recurrence. You should get O(N logN) from the extra merge step.

sebii
  • 506
  • 2
  • 6