# Big-oh expression help!

• 01-24-2011, 05:36 AM
borgan
Big-oh expression help!
I have two questions about big-oh expression.
The first one is:

for(i=1;i<n;++i)
for(j=1;j<floor(i/2);j++)
{
...statements that require exactly j operations...
};
For this one, i think that the number of operations written by big-oh operations is O(n^2)

for (i=1;i<n;++i)
{
...statements that require at most 10^9 /i operations
}
For this one, i do not understand the meaning of "at most 10^9 /i operations". Hope someone give me some suggestions. Thx.
• 01-24-2011, 05:12 PM
If you are calculating for the worst case, then you assume the inner statement uses 10^9/i operations. It depends on wether you are calculating for best, average or worst case performance - generally you consider worst case since in some algorithms, its a deal breaker even if unlikely.
• 01-24-2011, 05:20 PM
JosAH
Quote:

Originally Posted by borgan
For this one, i think that the number of operations written by big-oh operations is O(n^2)

for (i=1;i<n;++i)
{
...statements that require at most 10^9 /i operations
}
For this one, i do not understand the meaning of "at most 10^9 /i operations". Hope someone give me some suggestions. Thx.

That loop does M/1+M/2+M/3 ... +M/n operations where M == 10^9. 10^9 is a (large) constant so that loop does O(n) operations.

kind regards,

Jos