Confused on recurrence and Big O

Question

I know that T(n) = T(n/2) + θ(1) can be result to O(Log N) and my book said this is a case of Binary Search. But, how do you know that? Is it just by the fact that Binary Search cuts the problem in half each time so it is O(Log N)?

And T(n) = 2T(n/2) + θ(1) 

why is it that the result is O(N) and not O(Log N) when the algorithm divides in half each time as well.

Then T(n) = 2T(n/2) + θ(n)

can be result to O(N Log N)? I see the O(N) is from θ(n) and O(Log N) is from T(n/2)

I am really confused about how to determine the Big O of an algorithm that I don't even know how to word it properly. I hope my question is making sense.

Thanks in advance!

Answer 1

an intuitive solution for these problems is to see the result when unfolding the recursive formula:

Let's assume Theta(1) is actually 1 and Theta(n) is n, for simplicity

T(n) = T(n/2) + 1 = T(n/4) + 1 + 1 = T(n/8) + 1 + 1 + 1 = ... = 
= T(0) + 1 + ... + 1 [logN times] = logn

T'(n) = 2T'(n/2) + 1 = 2(2T'(n/4) + 1) + 1 = 4T'(n/4) + 2 + 1 = 
= 8T'(n/4) + 4 + 2 + 1 = ... = 2^(logn) + 2^(logn-1) + ... + 1 = n + n/2 + ... + 1 = 
= 2n-1

T''(n) = 2T(n/2) + n = 2(2T''(n/2) + n/2) + n = 4T''(n/4) + 2* (n/2) + n = 
= 8T''(n/8) + 4*n/4 + 2*n/2 + n = .... = n + n + .. + n [logn times] = nlogn

To formally prove these equations, you should use induction. Assume T(n/2) = X, and using it - prove T(n) = Y, as expected.

For example, for the first formula [T(n) = T(n/2) + 1] - and assume base is T(1) = 0
Base trivially holds for n = 1
Assume T(n) <= logn for any k <= n-1, and prove it for k = n
T(n) = T(n/2) + 1 <= (induction hypothesis) log(n/2) + 1 = log(n/2) + log(2) = log(n/2*2) = log(n)

Answer 2

I find an easy way to understand these is to consider the time the algorithm spends on each step of the recurrence, and then add them up to find the total time. First, let's consider

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

where n=64. Let's add up how much the algorithm takes at each step:

T(64) = T(32) + 1 ... 1 so far
T(32) = T(16) + 1 ... 2 so far
T(16) = T(08) + 1 ... 3 so far
T(08) = T(04) + 1 ... 4 so far
T(04) = T(02) + 1 ... 5 so far
T(02) = T(01) + 1 ... 6 so far
T(01) = 1         ... 7 total

So, we can see that the algorithm took '1' time at each step. And, since each step divides the input in half, the total work is the number of times the algorithm had to divide the input in two... which is log2 n.

Next, let's consider the case where

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

However, to make things simpler, we'll build up from the base case T(1) = 1.

T(01) = 1           ... 1 so far 

now we have to do T(01) twice and then add one, so

T(02) = 2T(01) + 1  ... (1*2)+1 = 3

now we have to do T(02) twice, and then add one, so

T(04) = 2T(02) + 1 ... (3*2)+1  = 7
T(08) = 2T(04) + 1 ... (7*2)+1  = 15
T(16) = 2T(08) + 1 ... (15*2)+1 = 31
T(32) = 2T(16) + 1 ... (32*2)+1 = 63
T(64) = 2T(32) + 1 ... (65*2)+1 = 127

So we can see that here the algorithm has done 127 work - which is equal to the input multiplied by a constant (2) and plus a constant (-1), which is O(n). Basically this recursion corresponds to the infinite sequence (1 + 1/2 + 1/4 + 1/8 + 1/16) which sums to 2.

Try using this method on T(n) = 2T(n/2) + n and see if it makes more sense to you.