Q:

Time complexity Recursive program

I can't figure out the time complexety of the following snippet of code: 
void  f( int N ){
   sum ++;
   if ( N   > 1){
      f( N /2);
      f( N /2);
   }

It's the double iteration that gives me problems.
I know (or think) that the time complexity of
void  f( int N ){
   sum ++;
   if ( N   > 1){
      f( N /2);
   }

is ~log2(N) but don't know what to do with the other code.

A:

You are calling the recursion twice on (N/2). Lets write the formula: 
T(n) = 2*(N/2) + 1

Using master theorem, we fall on the first case where:

a=2 
f = O(1)
b=2

T(n) = Θ(n)

We also find T(n) = 2*T(n/2) + 1 here, which shows it is bounded by O(n)

A:

A good way to solve this problem would be:

1. Finding the recurrence relation
For each call to f we have time complexity T(N). Each call contains:

A constant amount of work C: sum++, comparison N > 1, recursive calling overhead, etc.
2 recursive calls to f, each with time complexity T(N / 2).

Thus the recurrence relation is given by T(N) = 2T(N/2) + C.

2. Finding a solution by inspection
If we repeatedly substitute T(N) into itself, we can see an emerging pattern:

What is the upper limit of the summation, m? Since the stopping condition is N > 1, after repeated substitutions the requirement would be

Thus the summation equals (dropping the round-down, and the constant C because it is simply multiplicative):

3. Proof by induction

Base step: test if the summation result is correct for the lowest possible value of N, i.e. 2:

The result is consistent.
Recurrence step: confirm that if the summation is correct for N / 2, it is also correct for N:

Which is exactly our original recurrence relation.

Hence by induction, the summation result is correct, and T(N) is indeed Ө(N).

4. Numerical testing:
We can write code to confirm our result if needed:
function T(n) {
  return n > 1 ? 2 * T(floor(n/2)) + 1 : 1;
}

Results:
N           T(N)
-------------------------
2           3
4           7
8           15
16          31
32          63
64          127
128         255
256         511
512         1023
1024        2047
2048        4095
4096        8191
8192        16383
16384       32767
32768       65535
65536       131071
131072      262143
262144      524287
524288      1048575
1048576     2097151
2097152     4194303
4194304     8388607
8388608     16777215
16777216    33554431
33554432    67108863
67108864    134217727
134217728   268435455
268435456   536870911
536870912   1073741823
1073741824  2147483647

Graph:

A:

Let's try tracing through it:
Let N be 8.
1 + f(4) + f(4)
=> 1 + 2 + f(2) + f(2) + f(2) + f(2)
=> 1 + 6 + f(1) + f(1) + f(1) + f(1) + f(1) + f(1) + f(1) + f(1)
When n = 8; work = 15
Let N be 4.
1 + f(2) + f(2)
=> 1 + 2 + f(1) + f(1) + f(1) + f(1)
When n = 4; work = 7
Let N be 2
1 + f(1) + f(1)
When n = 2; work = 3;
Let N be 1
1
When n = 1; work = 1

So at a glance the work pattern seems to be 2n - 1
We still need to prove it!
From the algorithm the recursive relation is:
W(1) = 1
W(N) = 1 + 2 * W(N / 2)
Proof by induction
Base Case:
W(1) = 2(1) - 1 = 1 as required.
Recursive case:

Assume W(N / 2) = 2(n/2) - 1 = n - 1
W(N) = 1 + 2 * (N / 2)
Applying induction...
W(N) = 1 + 2(n - 1) = 1 + 2n - 2 = 2n - 1 as required

Therefore the complexity is O(2n - 1) because O is reflexive
=> O( max { 2n, -1 } ) because of the rule of sums

=> O(2n)
=> O(n) because of the rule of scaling

