Big-oh expression help!
I have two questions about big-oh expression.
The first one is:
...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)
...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.
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.
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.
Originally Posted by borgan