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.
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:
T(n) = Θ(n)
We also find T(n) = 2*T(n/2) + 1 here, which shows it is bounded by O(n)
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:
C: sum++, comparison N > 1, recursive calling overhead, etc.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:
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
This code is much similar to binary tree traversal,
void f( int N ){
sum ++;
if ( N > 1){
f( N /2); //like Traverse left subtree
f( N /2); //like Traverse right subtree
}
which basically traverses through each node once, with O(N) time complexity.
n/8
n/4 ---------
n/8
n/2 ------------------
n/8
n/4 ---------
n/8
n -------------------------------
n/8
n/4 ---------
n/8
n/2 ----------------
n/8
n/4 ---------
n/8
this goes on till the passed value becomes 1 or 0.
