CODEWITHSUNDEEP
big-otime-complexityasymptotic-complexity
Ammar Alyousfi
Ammar Alyousfi

Reputation: 4372

Find the computational complexity for the following loops

code

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)

Upvotes: 3

Views: 1677

Answers (2)

Mohamed Ennahdi El Idrissi
Mohamed Ennahdi El Idrissi

Reputation: 2977

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:

enter image description here

Upvotes: 2

templatetypedef
templatetypedef

Reputation: 372852

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, ..., 2log n. If we sum this up, using the formula for the sum of a geometric series, we get

1 + 2 + 4 + 8 + ... + 2log n = 2log n + 1 - 1 = 2 · 2log n - 1 = 2n - 1

So the total work done is Θ(n).

Hope this helps!

Upvotes: 2

Related Questions