CODEWITHSUNDEEP
big-ocomplexity-theory
George Kagan
George Kagan

Reputation: 6124

Simple while loop Big-O complexity

int a = 3;

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

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

Upvotes: 6

Views: 563

Answers (4)

Aryabhatta
Aryabhatta

Reputation:

Well, you could actually go into an infinite loop!

Assume 32 bit integers:

Try this:

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

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

An easy way to see this is:

xn+1 = xn2.

Take x1 = a.

Taking logs.

tn = log xn

Then tn+1 = 2tn

I will leave the rest to you.

It becomes more interesting if you consider the complexity of multiplication of two k digits numbers.

Upvotes: 2

sdcvvc
sdcvvc

Reputation: 25654

After i-th iteration (i=0,1,...) value of a is 32i. There will be O(log log n) iterations, and assuming arithmetic operations in O(1) this is time complexity.

Upvotes: 1

J&#246;rg W Mittag
J&#246;rg W Mittag

Reputation: 369458

The number of loop iterations is Ο(log log n). The loop body itself does an assignment (which we can consider to be constant) and a multiplication. The best known multiplication algorithm so far has a step complexity of Ο(n log n×2Ο(log* n)), so, all together, the complexity is something like:

Ο(log log n × n log n×2Ο(log* n))

In more readable form:

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

Upvotes: 1

John Kugelman
John Kugelman

Reputation: 361625

That's not right. a can't be a part of the big-O formula since it's just a temporary variable.

Off the top of my head, if we take multiplication to be a constant-time operation, then the number of multiplications performed will be O(log log n). If you were multiplying by a constant every iteration then it would be O(log n). Because you're multiplying by a growing number each iteration then there's another log.

Think of it as the number of digits doubling each iteration. How many times can you double the number of digits before you exceed the limit? The number of digits is log n and you can double the starting digits log2 log n times.

As for the other aspect of the question, yes, O(a-th root of n) could be a valid complexity class for some constant a. It would more familiarly be written as O(n1/a).

Upvotes: 8

Related Questions