while i <= n do
i = i ^ 2
x = x + 1
- -Aleck-Lv 51 decade agoFavorite Answer
- NelsonLv 51 decade ago
(i^2)^2...)^2 > n, and
we can see that x increases 1 in every single cycle
=> i^(2^x) > n
=> (2^x)log i > log n
=> x > log log n
And we can also have x-1 < log log n, in the same way
=> O(x) = O(x) - O(1) = log log n
2010-02-23 21:15:10 補充：
ouh, I didn't take the self multiplication into account. Even using fast Fourier I can only give out a very bad bound: (log n)((log log n)^2). The actual bound must be much lower.
2010-02-23 21:15:13 補充：
But this quite goes beyond the scope of high school students' understanding, so... I guess we can leave it as it is, problem solved, yeh!