What is the time complexity for this Algorithm?

Question

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?

You will do n * sqrt(n) operations, so the complexity is n^(3/2) — Fabinout
– Fabinout, Commented Jul 17, 2015 at 14:51
@Fabinout That is not correct. Why do you think you do sqrt(n) operations for the inner loop? — adao7000
– adao7000, Commented Jul 17, 2015 at 14:52
@Fabinout If this inner loop multiplied by two every time it would be n log n, this is even faster, n*sqrt(n) is way off track — user555045
– user555045, Commented Jul 17, 2015 at 14:53
@adao7000 you start at 2, then 4, then 16, then 256. So you're right, and I'm wrong, this wasn't a sqrt complexity. — Fabinout
– Fabinout, Commented Jul 17, 2015 at 14:55
Consider: What is the value of j after M steps? (Hint: nothing involving a !.) — Sneftel
– Sneftel, Commented Jul 17, 2015 at 14:56

Danstahr · Accepted Answer · 2015-07-17 14:54:49Z

4

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.

edited Jul 17, 2015 at 14:54

answered Jul 17, 2015 at 14:53

Danstahr

4,33925 silver badges38 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

adao7000 Over a year ago

Excellent explanation!

Fabinout Over a year ago

Good answer, it's important to note that the outer loop is just there to complexify the problem.

MattPutnam · Accepted Answer · 2015-07-17 14:54:38Z

1

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.

answered Jul 17, 2015 at 14:54

MattPutnam

3,0273 gold badges19 silver badges24 bronze badges

Collectives™ on Stack Overflow

What is the time complexity for this Algorithm?

2 Answers 2

2 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related