CODEWITHSUNDEEP
big-o
ninjaneer
ninjaneer

Reputation: 7031

Quick Big Oh calculation

I'm reviewing Big Oh notation. Is there such a thing as big oh order function: O(n * (n/2)) ? I just assumed that it would just be O(n^2) but these notes say differently (not my notes). The notes are referring to this code:

for(int i = 0; i < x; i++)
{
    for(int j = 0; j < x/2; j++)
    {
        halfsum += a[i][j];
    }
}

Upvotes: 2

Views: 168

Answers (2)

Neowizard
Neowizard

Reputation: 3027

In big-O notation it's true that O(n^2) = O(n^2 / 2), so of course O(n^2 / 2) exists, it's just a bit pointless to state the constant, so why bother? Its not that it's not correct, just meaningless.

It's just like in simple 6th grade math: X = X * 1. There's not point in writing down multiplication by 1, but it's not erroneous.

Upvotes: 0

skyjlv
skyjlv

Reputation: 17

You drop the coefficient so technically that is still O(n^2). In other words O((n^2)/2) = O(n^2).

Upvotes: 1

Related Questions