Question

What is the time complexity of this code?

I'm unsure if it is O(log(n)) or O(n).

I think that the while loop is logn but the for loop that comes after runs the same number of times as the while loop.

string toBinary(int num) { string binary = "", temp = ""; while (num != 0) { temp += to_string(num%2); num /= 2; for (int i = temp.size() - 1; i >= 0; i--) { binary += temp[i]; return binary;

Answer 1

while loop runs for O(log(n)) times

Then size of temp becomes log(n)

So, the for loop runs for size of variable temp times.
So, for loop is also runs for O(log(n)) times.

So, total time complexity
= O(log(n)) + O(log(n))
= O(log(n))