how to calculate time complexity in big O notation of this algorithm

I need help finding time complexity of this function in big O notation:

int myfunction(bool exists)
{
    int var=0; int k,j,n;
    if (exists)
       for(k=1; k<=n; k*=2)
          for(j=1; j<=k; j++)
             var++;
    else
       for(k=1; k<=n; k*=2)
          for(j=1; j<=n; j++)
             var++;
    return var;
}

from what I understood from the book, in cases like this when we have if-else blocks, the overall complexity of the algorithm is the worse case of the both blocks, so I calculated the else block complexity, which does have a complexity of O(log2(n)), correct me if I'm wrong, but I'm having trouble finding out the time complexity of the if block, it seems that it takes less time, but I can't determine how much.

---

A formal answer would be, separating the IF block and the ELSE block:

---

In the else case, you loop n*floor(log 2(n)) times. Since we want big-O, we take the worst case, where floor(log 2(n)) == log2 (n). Hence the else loop is O(n log2(n)). Actually I'd normally write O(n log(n)) here - in big O notation you don't put in constant factors, like the change of base of the log.

In the if case, the inner loop runs 1, 2, 4,...,2^x times, where x is floor(log2(n)). The total number of cycles is the sum of these numbers, ie 2^(x+1)-1. If you can't see this straight away, notice that 1, 2, 4, etc are just binary digits. If you fill those digits what is the total? You'll see that it's a binary number like 11111.

Hence the if loop takes 2^(floor(log 2(n)) + 1) - 1 steps; taking the worst case, this is 2^(log 2(n) + 1) - 1 = 2n - 1. Keeping the largest term, and dropping the constants, this is O(n).

链接地址: http://www.djcxy.com/p/39914.html

上一篇: 斐波纳契序列的生成

下一篇: 如何计算该算法的大O符号的时间复杂度