Finding time complexity of T(n) = 2T(n/2) + Logn

Question

T(n) = 2T(n/2) + Logn

This is the given time complexity and I am using recursive tree method to find it's time complexity.

For the first call it is doing : Log(n) work

For second it is doing: Log(n/2) + Log(n/2)

For second it is doing: Log(n/4) + Log(n/4) + Log(n/4) + Log(n/4)

And height of tree would be log(base2) n.

So I am summing the series till log(base2)n terms to get time complexity:

Log(n) + 2Log(n/2) + 4Log(n/4) + 8*Log(n/8) + ...... till log(base2)n terms.

I am getting O(logn) time complexity but it's correct time complexity is:O(n).

Can anyone tell me how to do it?

Answer 1

The steps you have taken in your analysis are correct. We indeed get:

log + 2log(/2) + 4log(/4) + 8Log(/8) + ...... + log(1)

It will be easier if we write this in a "bottom up" way, i.e. starting at the leaves that have a height of 0. If we consider the tree to be a perfect binary tree, then the bottom level has (+1)/2 nodes with a height of 0, the next level has (+1)/4 nodes with a height of 1, ...etc. We need to count a node's height as its cost (i.e., the log in the recurrence). For instance, if we only have one node, which is thus a leaf, the cost is log1, which is 0. If we combine these terms, we get:

0(+1)/2 + 1(+1)/4 + 2(+1)/8 + 3(+1)/16 + ...

Note that the terms are now ordered in opposite order from what you had, and the coefficients (0, 1, 2, 3, ...) are what you had as log() calls, while your coefficients (powers of 2) are here expressed as fractions of . That's the effect of doing it bottom-up instead of top-down. I'm sure it could be done also with a top-down approach, but I find this easier.

So in general we have (+1)/2^ℎ+1 nodes of height ℎ, and the cost (coefficient) for each of them is ℎ:

∑_ℎ=0^log ℎ(+1)/2^ℎ+1

We can move (+1) out of this summation:

(+1)∑_ℎ=0^log ℎ/2^ℎ+1

The summation has these terms: 0/2 + 1/4 + 2/8 + 3/16 + ... We can write this as a sum of sums of geometric series, like this:

1/4 + 1/8 + 1/16 + 1/32 + ...
      1/8 + 1/16 + 1/32 + ...
            1/16 + 1/32 + ...
                   ....
                   

Even if there are infinite terms, each line is a sum that converges. They would each converge to this:

1/2
1/4
1/8
1/16
...

This is again a geometric series, and its sum converges, ... to 1. As we have a limited number of terms, we can be sure the sum is less than 1.

So... the total expression, including the coefficient (+1), is O().