Find the computational complexity for the following loops

Question

For n=1 : Inner loop will execute 1 time.
For n=2 : Inner loop will execute 1+2 times.
For n=4 : Inner loop will execute 1+2+4 times.
For n=8 : Inner loop will execute 1+2+4+8 times.

. . .

So how can I find the computational complexity?

My answer is : Number of inner loop iterations = n+(n/2)+(n/4)+(n/8)+...+(n/n)

Answer 1

The total time complexity is Θ(n). To see this, note that the inner loop does Θ(i) work per iteration, and that i takes on the values 1, 2, 4, 8, 16, 32, ..., 2^{log n}. If we sum this up, using the formula for the sum of a geometric series, we get

1 + 2 + 4 + 8 + ... + 2^{log n} = 2^{log n + 1} - 1 = 2 · 2^{log n} - 1 = 2n - 1

So the total work done is Θ(n).

Hope this helps!

Answer 2

You can formally proceed like the following to obtain both the exact number of instructions that will execute, as well as the order of growth: