Calculate big O complexity of specific algorithm

Question

I'm currently struggling finding the big O complexity of the following source snippet:

private static long algo1(long n){
    long counter = 0;
    long i = 1;
    long x = 1;
    while(i < n){
        long a = 4*i;
        for (long j = a; j >= 1; j--) {
            x = x+j;
            counter++;
        }
        i = a/2;
    }
    return counter;
}

The outer while(i < n) seems to me to be of complexity log(n). But what's the complexity of the inner for loop?

Possible duplicate of [Big O, how do you calculate/approximate it?](https://stackoverflow.com/questions/3255/big-o-how-do-you-calculate-approximate-it) — Prune, Mar 20 '19 at 16:38

score 0 · Accepted Answer · answered Mar 20 '19 at 15:57

Inner loop is O(i). If you consider the steps it does, it will do 4 on first run, 8 on second, 16 on third... until you reach n. If you consider n to be a power of 2 to make math a bit easier, 4 + 8 + 16 + ... + n/4 + n/2 + n ... will be <= 2n. So all in all, your algorithm is O(n).

score 0 · Answer 2 · answered Mar 20 '19 at 16:38

First of all, note that you have a built-in counter that will record exactly how many iterations are run. Where is your experimentation on that factor? How does counter react as n increases to very large numbers? That, in an empirical nutshell, is the definition of complexity.

Consider your loop, not merely the header statement. The entire loop control is

i = 1
while i < n
    ...
    i *= 2    // i = 4*i / 2

The equivalent is

for (i = 1; i < n; i *= 2)

Thus, your inner loop is, indeed, O( log2(n) ).

In the inner loop, x is never used; you can drop that computation entirely. All the loop does is to count the quantity of iterations.

Call the routine with various values of n; print the results.

Calculate big O complexity of specific algorithm

2 Answers2