0
$\begingroup$

I have the recurrence of the form

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

This can be solved using master's theorem and if i use the results of the theorem, the recurrence evaluates to a time complexity of O(n). But if i think of it in terms of its tree, the input is reducing by half each time so we have a tree of logn height. Cost of each level is O(n). So we might have a complexity of O(nlogn). Now i am confused that is it O(nlogn) or O(n). Please help me.

$\endgroup$
2
$\begingroup$

In this problem, the input size at each level of recursion is reduced by a factor of 2. At our topmost level, we have $cn$ for some constant $c$, but in the second level? In picturing a tree, our top most level (our leaf node) has one child, $cn/2$. This child has a single child of its own: $cn/4$, and so on.

To get the time complexity for our recurrence relation, we have to sum up the work done in each layer of the tree. You state that each layer does $O(n)$ work, but this is where your mistake is. Each layer does half the work of the previous layer. Therefore we end up with the summation $\sum_{i=0}^{n}\frac{n}{2^i}$. This sum is asymptotically equivalent to $O(n)$. Therefore, the result you reached using the Master Theorem is correct.

$\endgroup$
  • $\begingroup$ Thanks a lot. This was a naive mistake made by me. More of a careless mistake. $\endgroup$ – Navjot Waraich Jul 17 '18 at 0:07

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.