Algorithms

Algorithms

1. Complexity

   • Space Complexity
     • How much memory the algorithm takes up
   • Time Complexity
     • How fast the algorithm runs

2. Orders

   • Use Big O Notation
     • O(n) normal time-as n increases, time taken increases
     • O(n^x)-Polynomial growth- time increases faster than n increases
     • O(x^n)- Exponential growth- BAD- only good for small n
     • O(n!)- Factorial growth- BAD, worse than exponential
     • O (log n)- logarithmic growth- as n increases, time taken increases, but not as fast as n

3. Sequences of unambiguous instructions for solving a problem

4. Problems

   • Intractable problems
     • Problems we can't solve for any but the smallest version of the problem
     • Halting problem
       • It is impossible to write a program that will determine if another program will terminate on a given input