-2

the task says, determine O, Ω, Θ for the following code:

void f1(int n) {
 int i;
 for (i = n; i > 0; i /= 2) {
 printf("%d\n", i % 2);
 }
}

Well I know loop is gonna repeat itself until i becomes 0, so i will be n , n/2, n/4 n/8...2/2,0,

I looked in the solutions and the answer to problem is O(log n), Ω(log n), Θ(log n),

Why is the answer log n?

Any help is greatly appreciated!

Petar
  • 11
  • 3
  • If you double n, what happens to the number of iterations? Similarly when you double n in log(n) it only goes up by 1 (log to the base 2). – Ian Mercer Oct 27 '19 at 21:37
  • Possible duplicate of [Big O, how do you calculate/approximate it?](https://stackoverflow.com/questions/3255/big-o-how-do-you-calculate-approximate-it) – Prune Oct 28 '19 at 04:29

1 Answers1

0

Pay attention: The for loop terminates when i==0.

Now, the value of i is decreasing by dividing it by 2, hence, lets assume after some k+1 divisions by 2, the value of i will turn 0. That means, the loop executed k times and then terminated.

Now, you can say that i = n/(2^k) before the loop terminates.

Note: here (2^k) means 2 to the power of k.

And before the loop terminates at i==0, the last execution of loop will be at i = 1.

Hence, n/(2^k) = 1.

Taking denominator to other side, n = (2^k)

Taking log base 2 at both side, log2(n) = log2(2^k) = k

Hence, k = log2(n), and as k is the number of times the loop executes, the time complexity is O(Log2(n)) and ignoring the constants i.e. base 2, O(Log(n)).

Pulkit Jatav
  • 114
  • 5