Big-O Notation Code Algorithm Analysis Homework

Question

for(int i=N; i>0; i=i/2)  
    irrelevant statement;

I am asked to find the complexity class and I am unsure of whether I am supposed to use Big-Omega notation or Big-O? But I am assuming that it is O(N/2) and then O(N) if I drop the constants.

for (int i=0; i<N; i++)  
    for (int j = i+1; j<N; j++)  
        irrelevant statement;

For this one I believe it is O(N) * O(N+1) -> O(N^2 + N) and then O(N^2) after I drop the N?

Answer 1

For the first one, how many more operations get executed if you double N?

Answer 2

You are right about the second one. First one is O(logN), and the second is O(N^2). But there is one but. What you refer to as irrelevant statement might be very relevant. If that statement were, for example a function call which in turn works in O(N), then the complexities would become O(N*logN) and O(N^3) respectively. So, you're right if the irrelevant statement is O(1).

Answer 3

The first one has complexity class O(log2(n)), as when you double n it only adds one more operation.

The second one is O((n^2)/2), or just O(n^2). The easiest way to understand this is to imagine it as a shape. You have two for loops, so you know that the ultimate complexity is n^2, but as the first continues, the second decreases to zero. This creates effectively a triangle.