I'm studying for an exam and have run into this problem:
j=n
while (j>=1) {
for i=1 to j
x= x+1;
j=j/2
}
The question is to derive theta notation for the number of times that x = x+1 is executed. To me this looks likes an nlog(n). Not sure if this is true or not. What techniques are recommended for analyzing this algorithm more mathematically? I mean like a step by step solution.
Any help would be greatly appreciated.
For loops that do not exit early, you can just use summations. For this, we want to transform all loops in simple for loops that count up in steps of one. This loop becomes a sum. So
For i = 1 to j
x = x + 1
Is O(j).
The outer loop then is
j = n
while (j >= 1) {
something with O(j)
j = j / 2
}
Observe how we can transform this into
for (i = 0; i <= log2(n); i++) {
something with O(n * 2^-i);
}
Let's express this again as a sum: O(sum from i = 0 to log2(n) of n * 2^-i).
From math, you might remember that `
sum from i = 0 to k of q^k = (1 - q^(k+1)) / (1 - q)
Lets apply it: O(n * 2 * (1 - 2^(-log2(n)-1))) = O(n * (2 - 1/n)).
As we are looking at big n -> inf: O(2 * n).
Big-O notation disregards constant factors: O(n).
You can calculate it in this way :
j = n
while(j >= 1){
......
j /= 2;
}
what is the complexity of it ?
j = n, n/2, n/4, n/8, ...., 1
j = n/(2^i), .... n/n
when will this loop stop ? when 2^i = n
n = 2^i , using log => i = log(n)
so it's log(n) but what about the inner loop ?
inner loop executes j times , j = 1, 2, 4, 8, .... , n ( in the example it's n .... 4, 2, 1)
so total work = Sum(2^k)[ k = 0, ... , i] where i = log(n) (geometric series)
[2^(log(n)) - 1]/[2 - 1] = (n - 1)/1 = O(n)
Methodically, using Sigma notation:
(Empirically verified).
You can analyze the complexity with a recurrence relation:
T(n) = n + T(n/2)
Describes the time complexity of the outer while loop. The first n represents the inner for loop, and the recursive term describes the remaining iterations. If you expand the relation, you get :
T(n) = n + n/2 + n/4 + ... + 1
With some summation tricks, you can find the closed form of this:
T(n) <= 2n - n/(2^(log(n)))
You can prove that 2n grows faster than n/(2^(log(n)) as n grows arbitrarily large, so your algorithm has complexity O(2n) = O(n)
