CODEWITHSUNDEEP
python-3.xtime-complexity
user7777777
user7777777

Reputation: 217

What is time complexity when power involed?

 def f1(lst):
     i=3
     while i<len(lst):
        print(lst[i])
        i **= 3

What is the time complexity of this code? the answer says O(loglogn), why?

Upvotes: 0

Views: 115

Answers (1)

Kiwi
Kiwi

Reputation: 2816

Take a look at how i grows with loop (^ means power here) :

i_0 = 3
i_1 = i_0^3 = 3^3
i_2 = i_1^3 = (3^3)^3 = 3^(3*3)
i_3 = i_2^3 = (3^(3*3))^3 = 3^(3*3*3)
...
i_n = 3^(3^n)

This is called iterated powers but it is not Tetration. As you can see, it is a nested exponentation so the time complexity would be the inverse function : O(log3(log3(n))).

Upvotes: 2

Related Questions