CODEWITHSUNDEEP
algorithmtime-complexity
Nariman Esmaiely Fard
Nariman Esmaiely Fard

Reputation: 635

What is the time complexity for this Algorithm?

for i = 1 to n do
    j = 2
    while j < i do
        j = j * j

I think it's time complexity is : log(n!) = n * log(n).

but solution said that it is : n * loglog(n) and I didn't understand why?

Upvotes: 3

Views: 289

Answers (2)

Danstahr
Danstahr

Reputation: 4319

In the explanation below, I assume that all arithmetic and comparison operations are O(1).

for i = 1 to n do

The below is repeated N times, which makes the n * part in the solution.

    j = 2
    while j < i do
        j = j * j

The above calculates the first number of the following sequence that's >= i : 

2 = 2^(2^0)
4 = 2^(2^1)
16 = 2^(2^2)
256 = 2^(2^3)
65536 = 2^(2^4)
...

So the only thing you need to do is to find the relation between i and 2^(2^i). And log(log(2^(2^i))) = log(2^i) = i.

Upvotes: 4

MattPutnam
MattPutnam

Reputation: 3017

Let's break it down and work from the inside out.

Imagine the following:

j = 2
while j < n do
  j = j * 2

j goes 2, 4, 8, 16..., so if n doubles in size, it only takes roughly one more iteration for j to surpass it. That's basically the definition of logarithmic.

The inner loop in your case is a bit different:

j = 2
while j < n do
  j = j * j

Now j goes 2, 4, 16, 256, 65536... and surpasses n even more easily. In the first case, j was growing exponentially per iteration, now it's growing doubly exponentially. But we're interested in the inverse--j surpasses n in log(log(n)) steps.

Then the outer loop just means you do that n times.

Upvotes: 1

Related Questions