Question

Analyze the following code and provide a "Big-O" estimate of its running time in terms of n. Explain your analysis.

for (int i = n; i >= n; i = i/2)

          some O(1) time statements;

end for

Answer 1

O(1)

for(int i = n; i >=n; i =i/2)

start condition go until counter is decrementing by 2

in first iteration loop will succeed after that loop condition will fail and loop will run only one time.

eg.,

#include <iostream>
using namespace std;

int main() {
   int n = 32;
   int x = 1;
   for(int i = n; i >=n; i =i/2){
   cout<<"running"<<x<<"times"<<endl;
   x++;
   }
   return 0;
}

consider the above snippet of code., the print statement will run only one time. as in first iteration i = 32 which is validating loop test condition. but in next iteration i = 16 and will exit loop. So the loop will run only one time. Hence time complexity of the loop is O(1)