[Solved] Time complexity of Integer.toBinaryString() in Java

Question

There are two ways to look at this:

Integer.toBinaryString(n) produces a string of length ceiling(log2(n)). That computation will take time that is roughly proportional to log(n).
The maximum value for n is 2^31 – 1, and that computation will always take less than some fixed constant time.

In fact, the question of the big O complexity of Integer.toBinaryString(n) is not mathematically meaningful. By definition, big O complexity is about a function’s behavior as some variable tends to infinity. And the only variable ( n ) cannot do that in this context.

Accepted Answer

There are two ways to look at this:

Integer.toBinaryString(n) produces a string of length ceiling(log2(n)). That computation will take time that is roughly proportional to log(n).
The maximum value for n is 2^31 – 1, and that computation will always take less than some fixed constant time.

In fact, the question of the big O complexity of Integer.toBinaryString(n) is not mathematically meaningful. By definition, big O complexity is about a function’s behavior as some variable tends to infinity. And the only variable ( n ) cannot do that in this context.