# What is time complexity in this case?

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.

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.