Simple Big-O Loop Complexity

Question

int a = 3; while (a <= n) { a = a * a; } 

My version is that its complexity is as follows:
http://www.mmoprophet.com/stuff/big-o.jpg
Is there such a thing?

Answer 1

This is not true. a cannot be part of the big-O formula, because it is just a temporary variable.

On top of my head, if we take multiplication by a constant-time operation, then the number of multiplications performed will be O (log log n) . If you multiplied by a constant for each iteration, then that would be O (log n). As you multiply an increasing number by each iteration, there is another log.

Think of it as the number of digits doubling each iteration. How many times can you double the number of digits before the limit is exceeded? The number of digits is log n, and you can double the logbook twice ₂ log n times.

---

Regarding another aspect of the question, yes, O (the a-th root of n) may be an admissible complexity class for some constant a. It would be better written as O (n ^{1 / a} ) .

Answer 2

Well, you could go on an endless loop!

Assume 32-bit integers:

Try the following:

 int a = 3 ; int n = 2099150850; while (a <= n) { a = a*a; } 

But assuming there are no integer overflows, the other posters are right, this is O (log logn), if you are assuming O (1) multiplication.

Easy way to see this:

x _{n + 1} = x _n ² .

Take x ₁ = a.

Take the magazines.

t _n = log x _n

Then t _{n + 1} = 2t _n

I will leave the rest to you.

This becomes more interesting if you consider the difficulty of multiplying numbers by two k digits.

Answer 3

The number of loop iterations is & Omicron; (log log n). The body of the cycle itself performs the task (which we can consider constant) and multiplication. The most famous multiplication algorithm still has complex complexity & Omicron; (n? thinsp; log? thinsp; n? 2? ^{Omicron; (log * ? thinsp; n)} ), so collectively the complexity looks something like this:

& Omicron; (enter enter n & thinsp; & t; & thinsp; n & thinsp; enter & thinsp; n & times; 2 ^{& Omicron; (enter * & thinsp; n)} )

In a more readable form:

Ο (log log n × n log n × 2 ^ Ο (log * n)) http://TeXHub.Com/b/TyhcbG9nXGxvZyBuXCxcdGltZXNcLG4gXGxvZyBuXCxcdGltZXNcLDJee08oXGxvZ14qIG4

Answer 4

After the ith iteration (i = 0,1, ...) the value of a is 3 ^{2 i} . There will be iterations of O (log log n), and assuming arithmetic operations in O (1), this is a temporary difficulty.