Algorithms and Complexity

Correct VS Incorrect algorithm

1. Correct algorithm
-> Translates every input into the correct output.

2. Incorrect algorithm
-> If there is at least one input instance for which the algorithm does not produce the correct output.

Fast VS Slow algorithms

• Complexity of Algorithms

  • Intuitive approach: Estimate the running time of an algorithm
    - Use execution times (run time): dependent on implementation and hardware.
  • Better Approach: count the number of operation
    - # additions, #comparision, #assignment

Implementation : influenced by skill programmer
Hardware: changes the whole time and highly diverse

• Description of the running time of an algorithm

1. Big O notation → upper bound for number of operations
   

2. Ω notation → lower bound for #operations
   

3. ⍬ notation → exact bound for #operations
   

• Running time of Maximum algorithm

1. Strict bound: ⍬(n)
   • Upper Bound: O(n^2)
   • Lower Bound: Ω(1)
2. In practice (for polynomial functions)
   • Ignore constants for a sufficiently large problem size
   • Keep only term with highest degree

Typical functions for running time

1. Logarithmic function
   → #operations grows very slowly
   

2. Exponential function
   → #operations grows very fast
   

   • In practice, we have to avoid running time complexity of exponential function

3. Example: polymerase chain reaction (PCR)