10

We did an exercise in class today dealing with big-O notation. Here is one of the problems:

void modifyArray(int a[], int size)
{   
    int max = a[0];
    for (int i = 1; i < size / 2; ++i)
    {
        if (max < a[i])
        max = a[i];
    }
    for (int j = 1; j <= size * size; ++j)
    {
        ++max;
        cout << max;
    }
}

My intuition tells me that f(n) = n/2 + n2 = O(n2) but according to my professor the answer is simply O(n). Could anyone explain to me why and when we just change what we consider to be the input size?

I understand that it is not a nested loop -- that is not what is confusing me. I don't understand why for a given input size, the second loop is only considered to be O(n). The only way I can make sense of this is if we isolate the second loop and then redefine the input size to simply being n = size^2. Am I on the right track?

3
  • Because you can remove the second loop and simply write max += size * size Nov 6, 2013 at 6:00
  • Well the code in the question is clearly O(n^2), but after optimization it's O(n). However, did the professor say anything about that? Nov 6, 2013 at 6:03
  • 4
    Thanks for the responses. I really like your lines of thinking; however, I interpreted the exercise instructions as taking the code at face value, regardless of how "useless" (or inefficient, for that matter) the code seemed. Nov 6, 2013 at 6:09

3 Answers 3

4

If the code you present is exactly the code your professor is commenting on, then (s)he's wrong. As written, it outputs each number from 1 to size * size, which is definitely O(n^2), as n = size is the sane choice.

Yes, you're right to think you could say something like "O(n) where n is the square of the array size", but that's complication without purpose.

As others have said, if the cout << max is removed, the compiler may optimise out the loop to a single O(1) assignment, meaning the function's other O(n) operation dictates the overall big-O efficiency, but it may not - who said you're even enabling optimisation? The best way to to describe the big-O efficiency is therefore to say "if optimisation kicks in then O(n) else O(n^2)" - it's not useful to assert one or the other then hide your assumptions, and the consequences if they're wrong, in a footnote.

3

Consider this example:

for (i = 0; i < N; i++) {
    sequence of statements
}
for (j = 0; j < M; j++) {
    sequence of statements
}

The first loop is O(N) and the second loop is O(M). Since you don't know which is bigger, you say this is O(max(N,M)).

In your case N=size/2 and M=size*size.

O(max(N,M)) becomes O(max(size/2,size*size)) which is O(size*size). so f(n)=O(size^2)=O(n^2)

for the problem you are asking; yeah i think, what you think is correct. redefine the input size to simply being n = size^2. that should be the way to consider it as O(n).

1

Actually the second loop can be done away with.

If you do not consider outputting intermediate terms, then

It is equivalent to max += size*size.

Then the code complexity shall reduce to O(size/2) ~ O(size).

Your Answer

Reminder: Answers generated by Artificial Intelligence tools are not allowed on Stack Overflow. Learn more

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.