Complexity

Program Efficiency

• best case performance
  
• worst case performance
  
• average case performance
  

Units

T(n) <= c * (n2)
O(n)

Definition:

Rules for Order Arithmetic:

• Multiplicative Constants
  O(k * f(n)) = O(f(n))
• Addition Rule
  O(f(n) + g(n)) = max(f(n), g(n))
• Multiplication Rule
  O(f(n) * g(n)) = O(f(n)) * O(g(n))

Examples:

O(1000n) = O(n)

O(n2 + 3n + 2) = O(n2)

O(3n3 + 6n2 - 4n + 2) = O(3n3) = O(n3)

Return to CIS 350 Index Page