# Thread: Big-oh expression help!

1. Member
Join Date
Jan 2011
Posts
1
Rep Power
0

## 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.

2. 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.

3. 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

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•