Search code examples
algorithmanalysis

How could I determine the worst case in this code?

for(i=1;i<=n;i++) {
        
    if((i&(i-1))==0) {      
        
        for(j=1;j<=i;j++) {
            f();
        }
    } else {
        f();
    }
    
}

I did some test cases of this code and when i = 2^(i-1) the second for is executed, how could I determinate the big O notation, I think it could be O(n^2). f() is O(1), and how could I get the amortized analysis

Solution

  • When i is a power of 2, the inner loop performs exactly i calls to f. Otherwise, there is a single call.

    If n is a power of 2, let 2^m, we have a total of

    1 + 2 + 4 + ... n + n - m

    calls and this is

    3n - 1 - lg(n).

    On average (per iteration of the main loop), this is asymptotic to 3.

    Now if n = 2^m + n' with n' < 2^m, the count is

    1 + 2 + 4 + ... + 2^m + 2^m + n' - m = 3.2^m - 1 + n' - m = 3.n - 2.n' - 1 - Lg(n - n')

    which is still amortized 3 at worse but goes down to 2 for some n.