Algorithm Efficiency

Algorithm Efficiency

1. Time Efficiency

   • Time Complexity
     • run time of an algorithm as a function of its input
       • commonly expressed using O(...) notation
         • e.g. f(n) is O(g(n)) if there are positive constants c and n* such that: f(n) ≤ c.g(n) for n ≥ n*
           • i.e. growth rate of f(n) never exceeds that of g(n)
             • if f(n) is O(g(n)), then g(n) is Ω(f(n))
         • also Ω notation
           • e.g. f(n) is Ω(g(n)) if there are constants c > 0 and n* ≥ 1 such that: f(n) ≥ c.g(n) for n ≥ n*
             • i.e. the growth rate of f(n) is never less than that of g(n)
         • also Θ notation
           • e.g. f(n) is Θ(g(n)) if there are constants c*, c' > 0 and n* ≥ 1 such that: c*.g(n) ≥ f(n) ≥ c'.g(n) for n ≥ n*
             • i.e. f(n) and g(n) grow at the same rate
     • aka. growth rate
     • counting basic operations
       • arithmetic operations
       • assignments
       • conditional evaluation
       • array access
       • return statement
       • state clearly what you assume to be the basic operations

2. Space Efficiency