Is complexity of the following two recurrances same?

Question

I have two recurrance relations as:

T(n) = T(n/2) + c       // complexity O(logn)

T(n) = 2T(n/2) + c      // is the complexity O(logn)????

c is a constant in both case i.e. we are doing constant work in the merge part of recurrance.

First recurrance is of Binary Search where we are continuously discarding one half of array.

Let say second recurrance finds the max element from an array that is unsorted and we are dividing the array in two parts in each step, then comparing the result of each part to give a single max value.

In the first case we are not traversing the whole array. In the second we are traversing the whole. Now if i build a recursion tree for both i would get a complexity of O(logn) as the height of both the trees are same. If i am wrong please correct me. It is a confusion in my mind, so please help me clear it.

Answer 1

It's not the same complexity. The second one would be something like O(n)

A simple way to see this is to fix c = 0 and T(1) = a (whare a is a constant).

Then:

T(2) = 2T(1) = 2a
T(4) = 2T(2) = 4a
T(8) = 2T(4) = 8a
...
T(n) = n*a

You can see a linear complexity.