# Analysis of Algorithms

##### Introduction

The term analysis of algorithms is the calculation of the amount of storage/time are necessary to execute them. The term was original created by Donald Knuth.

##### Worst, Best & Average Case

The worst-case runtime complexity of an algorithm is the maximum number of steps taken on any instance of size n. the best-case runtime complexity of an algorithm is the minimum number of steps taken on any instance of size n. the average case runtime complexity of an algorithm is the average number of steps taken on any instance of size n.

For example consider sequential search algorithm that is searching an array of n numbers.

• The worst-case runtime complexity is O(n)
• The best-case runtime complexity is O(1)
• The average case runtime complexity is O(n/2)=O(n)
##### Asymptotic Notations Image by Cmglee

The goal of computational complexity is to classify algorithms according to their performances. We will represent the time function T(n) using the "big-O" notation to express an algorithm runtime complexity. For example, the following statement

T(n) = O(n2) says that an algorithm has a quadratic time complexity.

##### Definition of "big Oh"

Big O is the theoretical measure of the execution of an algorithm.

##### Constant Time: O(1)

An algorithm is said to run in constant time if it requires the same amount of time regardless of the input size.

##### Linear Time: O(n)

An algorithm runs in linear time if its time execution is directly proportional to the input size.

##### Logarithmic Time: O(log n)

An algorithm runs in logarithmic time if its time execution is proportional to the logarithm of the input size.