Algorithm Analysis

Question

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

Answer 1

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)

Answer 2

That's actually O(n)

You can figure this out as follows:

• The number of operations is the sum of the series 2, 4, 8, 16, 32, ...... which stops just before n.
• The sum of this geometric series is approximately in the range from n to 2n.
• Hence the whole algorithm is O(n) since you can ignore the constant factor.