Big-O Examples

Big-O notation is used to classify running-time functions. If f(n) is O(g(n)) then, informally, f(n) is within a constant factor of g(n).

Definition Let f(n) and g(n) be two functions on positive integers. We say f(n) is O(g(n)) if there exist two positive constants c and k such that f(n) <= cg(n) for all n >= k.

Examples:
• f(n) = 10n + 5 and g(n) = n
  

  f(n) is O(g(n)) 
  To show f(n) is O(g(n)) we must show constants c and k such that
       f(n) <= cg(n) for all n >=k
  or:  10n+5 <= cn  for all n >= k
  We are allowed to choose c and k to be integers we want as long as they 
  are positive.  They can be as big as we want, but they can't be functions
  of n.
  
  Try c = 15.  Then we need to show: 10n + 5 <= 15n.
               Solving for n we get: 5 <= 5n  or 1 <= n.
  So f(n) = 10+5 <= 15g(n) for all n >= 1.  (c = 15, k = 1).
  Therefore we have shown f(n) is O(g(n)).
  

• f(n) = 3n² + 4n + 1. Show f(n) is O(n²) Using the facts given in class, we know that:

  	4n <= 4n2	for all n >= 1
  and	1 <= n2	for all n >= 1

  so	3n2 + 4n + 1	<= 3n2 + 4n2 + n2 for all n >= 1
  		<= 8n2 for all n >= 1

  So we have shown f(n) <= 8n² for all n >= 1
  so f(n) is O(n²). (c = 8, k = 1)