Homework: How do i calculate the time complexity of this function?

Question

void func(int n){
    int i=1, k=n;
    while (i<=k){
        k=k/2;
        i = i*2;
    }
}

How do i calculate the time complexity of this function? I understand that the assignment of i=1, k=n takes two basic steps and to divide the value of k and multiply the value of i takes two basic steps as well, but because the values of i and k are increasing and decreasing exponentially, will the time complexity be O(log base 4 N) or O(log base 2 sqrt(N))?

Answer 1

Your answer is O(log √n), in the comments @Eraklon says it's O((log₂ n)/2), and @matri70boss says it's O(log₄ n). All three of you are correct, but the answer in its simplest form is O(log n).

• log √n = log n^0.5 = 0.5 log n, and we discard the constant factor 0.5 when we write in big O notation.
• (log₂ n)/2 = (log n)/(2 log 2) by the change of base identity, and 1/(2 log 2) is another constant factor we can discard.
• Likewise, log₄ n = (log n)/(log 4), and we can discard the constant factor 1/(log 4).