Is the time complexity / Big O of this function constant?

Question

Is the time complexity of this program O (1)?

f1(int n){ int temp = n; while (temp /= 2)) { len++; result+=m; } } 

and if we change int temp to double temp, will the time complexity change or will it remain constant?

 f2(int n){ double temp = (double)n; while (temp /= 2)) { len++; result+=m; } } 

Answer 1

The answer for the integer part is O(log n) , because the value is halved every time.

The dual version starts in the same way, except that when the value reaches 1 or close to 1, it does not stop and divides until underflow makes it 0. At this stage, the number of divisions is fixed.

I made a small empirically calibrated program that tries to predict the number of cycles:

 #include <stdio.h> #include <math.h> void f2(int n){ int len=0; double temp = (double)n; while (temp /= 2) { len++; } // 1.53 is an empiric constant, maybe it could be theorically computed // it was just to make the numbers match printf("%d %lf\n",len,log(n)*1.53+1074); } int main() { f2(100000000); f2(10000000); f2(1000000); f2(10000); f2(100); f2(1); } 

I get:

 1101 1102.183642 1097 1098.660686 1094 1095.137731 1087 1088.091821 1081 1081.045910 1074 1074.000000 

So the complexity is O(log n) plus an incompressible number of iterations, depending on the machine.

(my apologies for the empirical aspect of my answer, I'm not a floating point expert)

Answer 2

In order for the algorithm to have constant complexity in time, its execution time must remain constant, since the number of inputs n grows. If your function at n = 1 and n = 1000000 performs different time intervals for running, your function is not O(1) , that is, it does not have constant time complexity.

Let me calculate how many steps the first function takes to complete:

n / 2 ^x = 1 → x = log (n)

However, secondly, theoretically it will continue to divide n by 2 forever, but in fact it will stop after some steps log(n) + c , in which case the constant will be omitted, and the complexity will again be log(n) .