def f(n):
i = 2
while i < n :
i *= i
My solution : So what I did was I looked at the sum of the i *= i and I found out that it looks like this :
4^(0.5) + 4^(1) + 4^(2) + 4^(3) + ... + 4^(k) , and the loop stops whenever 4^k >= n and got that k=log(n), and so the time complexity is O(log(n)).
The answer was O(log(log(n))), after a while of thinking I found out that I could have written my sum as 2^(2^k)=4^k , and got the desired answer.
As I am still new in solving these solutions, and trying my best to understand them deeply so I don't repeat my mistakes, I want to know where is my mistake, aren't these two sums equal? am I missing something?
I appreciate any explanation. Thanks in advance :).
与恶龙缠斗过久,自身亦成为恶龙；凝视深渊过久,深渊将回以凝视…
