What is the complexity of this algorithm?

Getting Help
1

What is the complexity of myFunc ?

func myFunc(n int) int {
res := 0

for i := n; i > 0; i /= 2 {
    for j := 0; j < i; j++ {
         res++
    }
}

return res

}

I believe it to be O(n), am I wrong ?

2

If it were O(n), then it would never return a value greater than the half of the n you put into it.

But in fact, it’s much more.

I’m not sure though if this is O(n log n) or O(n²).

3

I think O(n) because the first time the outer loop runs n operations will be made, the second time n/2, the third time n/4, and so on.

So by adding n (1 + 1/2 + 1/4 + 1/8 + …) <= n * 2. Therefore O(n).

Am I mistaken with this ?

4

For the algorithmic complexity it is irrelevant if you divide n by something or not. Any constant factor can be treated as 1.

So you are running 2 loops, an inner and an outer. The outer one runs an amount of times that is determined by your parameter, so it is O(n*x) where x, is the complexity of the inner loop. Its complexity is not constant time. So your algorithm cant be O(n).

5

The outer loop runs log2(n) times. The inner loop is O(n). So O(n log n)?

6

I doubt it, as the total number of operations will be n * (1 + 1/2 + 1/4 + …) < 2 * n

7

It’s definitely not O(n²), actually O(n logn) is an upper bound, as this (replacing i with n on the inner loop) has that complexity:

for i := n; i > 0; i /= 2 {
    for j := 0; j < n; j++ {
         res++
    }
}

The outter loop is O(log n) (it’s basically the same as doing a binary search), so depending on the inner one, the whole thing could certainly be O(n). On the other hand, if we did just one run of the outter loop, it’d be the same as this:

for j := 0; j < n; j++ {
    res++
}

That’s clearly O(n), so that’s a lower bound. That should be clear, as the inner loop is not constant, so the whole thing can’t be O(logn).

So let’s see the inner one. Its complexity depends on i, which is dynamically changed by the outter loop. Now, my complexity calculations are a bit (more like really) rusty, but my first guess would be that it’s actually O (n / logn). Why? Because the loop really does i operations, which considering the outter loop, starts at n, but that n decreases logarithmically.

So, if the second complexity is right, we have that the whole complexity is O(logn * n / logn), which is the same as O(n). Of course this separation is a bit rough and probably not a very good explanation, as the inner loop is actually O(i) and we need to take into account that i is a function of n to get to the O(n / logn) complexity I’m thinking of.

Now, if instead of all this we actually counted the operations in terms of n, I think John is correct: we start by doing n operations, then n/2, and so on, rendering it lower than 2*n and higher than n, and thus O(n) again.

Now, though I had a fair share of courses dealing with maths involved in computer science when I studied my degree, as I said, that was some years ago and I haven’t really taken this to the white board. So take my intuition with a grain of salt and do the proper maths if you need to be sure. Also, please correct any blunder I may have committed.

8

This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.