Yahoo Answers is shutting down on May 4th, 2021 (Eastern Time) and beginning April 20th, 2021 (Eastern Time) the Yahoo Answers website will be in read-only mode. There will be no changes to other Yahoo properties or services, or your Yahoo account. You can find more information about the Yahoo Answers shutdown and how to download your data on this help page.
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!