Big O
Big O
Big O
1. Assume that each of the expressions below gives the processing time T (n)
spent by an algorithm for solving a problem of size n. Select the dominant
term(s) having the steepest increase in n and specify the lowest Big-Oh
complexity of each algorithm.
0.01n + 100n2
2n + n0.5 + 0.5n1.25
2. The statements below show some features of “Big-Oh” notation for the
functions f ≡ f (n) and g ≡ g(n). Determine whether each statement is
TRUE or FALSE and correct the formula in the latter case.
Rule of sums:
O(f + g) = O(f ) + O(g)
Rule of products:
O(f · g) = O(f ) · O(g)
Transitivity:
if g = O(f ) and h = O(f )
then g = O(h)
If it is FALSE then
Is it TRUE
Statement write
or FALSE?
the correct formula
Rule of products:
O(f · g) = O(f ) · O(g) TRUE
5n + 8n2 + 100n3 =
5n + 8n2 + 100n3 = O(n3 )
O(n2 log n) FALSE