time complexity of recursive function

[maryt]

Hello. I would like to ask the time complexity of this function. Can you please provide a method of calculating the complexity?

  int guesswhat(int n, int k){
	if (k==0) return(1);
	else return (n*guesswhat(n, k/2));
	
 } 

[jonnin]

recursion is just a form of iteration and works the same way.

this looks like lg(k), right? it iterates until k is 0. so if K is 1 million, it does (approximate vals) 1m, 500k, 250k, 125k, 62k,31k,15k … 0 about 20 times and 2^20 is about 1M … N is effectively a const in your loop

[maryt]

thank you. I was just confused at first, because we multiply the result of the recursive function by n and I was torn between n*log(k) and log(k).

Thank you!

[jonnin]

you are welcome.
Even if the loop changed N, the answer is the same for this code: the key is that the ITERATION is controlled ONLY by k. If n were part of the iteration control, it would be part of the answer too.