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
Graph showing time & complexity

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.

Quadratic Time: O(n2)

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

Definition of "big Omega"

Big omega is the notation that is used to define the lower bound.

Space Complexity

Space complexity is a measure of the amount of working storage an algorithm needs. That means how much memory, in the worst case, is needed at any point in the algorithm. As with time complexity, we're mostly concerned with how the space needs grow, in big-Oh terms, as the size N of the input problem grows.