Algorithms

Understand and analyse algorithms with time and space complexities.

What is an algorithm?

An Algorithm is a step by step procedure to solve a computational problem. It is different from a computer program which is a set of instructions to be given to a machine, an algorithm is written in simple English like statements for human understanding.

Time complexities of loops

The degree of polynomial is used to write the time and space complexities in big O notation.

Loop	Time complexity
for (i=0; i<n; i++)	\(O(n)\)
for (i=1; i<n; i*=2)	\(O(\log_2 n)\)
for (i=1; i<n; i*=3)	\(O(\log_3 n)\)

Classes of functions

Big O	Time
\(O(1)\)	Constant
\(O(\log n), O(n \log n)\)	Logarithmic
\(O(n)\)	Linear
\(O(n^2)\)	Quadratic
\(O(n^3)\)	Cubic
\(O(2^n), O(3^n), O(n^n)\)	Exponential

Compare classes of functions

(1)\[1 < \log n < \sqrt n < n < n \log n < n^2 < n^3 < ... < 2^n < 3^n < ... < n^n\]

Asymptotic notations

Big O - upper bound (also used when theta Θ could not be used)
Omega (Ω) - lower bound
Theta (Θ) - average bound (useful)