How to calculate time complexity

[krishan22]

Hi, I have a doubt to calculate time complexity for while loop. For example:

int n=5;
int count=0;
while(k<=n){
k=k*2;
}
cout<<count<<endl;

So here the answer is O(logn)?

Also how to calculate time complexity for the for loop and while. ex:

int n=8;
for(int i = 0; i<=n; i++) {
	
	while( n>= 1) {
		n = n/2;  
	}
}
 

Please help me, I am studying for exam.
Thanks in advanced

[jsmith]

In your first example, how many times will line 4 be executed? Write it as a function of n. Whatever your
formula is, that's the time complexity.

Assuming k starts at 1, the first time through k becomes 2. The second time through it becomes 4. The
third time through it becomes 8. It stops there. This is clearly logarithmic; line 4 will execute O( log2(n) )
times.

Now you do the second example. There is a subtlety there. First, figure out how many times the while()
loop will execute if n == 8. Then, figure out how many times the for() loop will execute.

[krishan22]

Thanks... I figure out that while loop will execute 4 times, so after while loop exited the n will be less than zero. So finally for loop will execute only once...

I think I am correct...

[krishan22]

Actually it should be like this, because it's look like sense.

int n=8;
int j;
for(int i = 0; i<n; i++) {
	j=n;

	while( j>= 1) {
		j =j/2;
		  
	}
}

So, now formula should be nlog(n)

Thanks....!