So I understand a little bit of algorithm analysis, but I'm at a complete loss to understand how to do this one. Can someone please explain this to me? Would this be O(logn)?
for (int i=1; i < n; i*=2)
for (int j=0; j < i; j++)
// do simple operation
To find the big O of the nested loops, you need to do steps like the following example.
For example, let:
n = 10
now the outer loop executes 3 time that is:
i=2,4 and 8
and inner loops executes 3 time for each iteration like
i=2 it iterates 2 times
i=4 it iterates 4 times
i=8 it iterates 8 times
so the total number of iterations are less the 2*n which makes it O(2n) we can neglect the constant factor so its big O is
O(n)
That's actually O(n)
You can figure this out as follows:
n. n to 2n. O(n) since you can ignore the constant factor.
i of each loop. E. g. 2 + 4 + 8 + 16 etc... the sum will always be between 1/2 n and 2 n. If n = 4 then the sum of all i = 2. If n = 129 then the sum of all i = 254.
O(n^2) - you need to do the sum of a geometric progression. It would be O(n^2) if it was an arithmetic progression, but that is not the case here.I will first calculate little-o for you to understand the whole process and then we will get big-O from it.
Let's take it into parts:
for (int i=2; i < n; i*=2)
First we have 1 bound from i=2
If i*=2 then i ={2,4,8,16,32,64...} so i increments following 2^x then:
We are looking for i > n to be true so it is 2^x > n whats needs to be true, doing a little of maths:
log2(2^x) = log2(n)
x=log2(n) //Here we figured out that i will need log2(n) loops to satisfy conditional statement.
Since in the for we have comparisons and bounds it will be 2log2(n)+1 operations for this for.
Notice: since this is a nested chain each operation in the following for will be multiplied 2log2(n)+1 times
for (int j=0; j < i; j++)
j=0 1 bound
j++ j={0,1,2,3,4,5,6,7,8....} so j=n then it goes 2n+1 for this for
Finally we have that little o is equal to:
(2n+1)*(2log2(n)+1)
4nlog2(n) + 2n + 2log2(n) + 1
log2(n)(4n+2) +2n +1
It turns out that o(log2(n)(4n+2) +2n +1), and in order to get big O we can reduce this expression neglecting some factors, then:
O(log2(n)n)
Hope it is clear enough to understand.
Regards.
Formally, you can proceed like the following:
