CODEWITHSUNDEEP
time-complexitybig-ocomplexity-theory
Tan Yu Hau Sean
Tan Yu Hau Sean

Reputation: 625

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

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))?

Upvotes: 0

Views: 111

Answers (1)

kaya3
kaya3

Reputation: 51162

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

  • log √n = log n0.5 = 0.5 log n, and we discard the constant factor 0.5 when we write in big O notation.
  • (log2 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, log4 n = (log n)/(log 4), and we can discard the constant factor 1/(log 4).

Upvotes: 2

Related Questions