Complexity Analysis

A way of comparing different algorithms. Algorithms’ time to run is hard to measure exactly and hard to compare with fairness. And also there are too many uncontrollable variables in measuring the actual time. Because of that, the algorithms are analyzed asymptotically: a way of measuring the performance of an algorithm without depending on hardware.

Cons of complexity analysis

• The algorithm might not reach the limit after which the asymptotic behaviour is seen
  Different algorithms can be used for different input ranges
• The input density and input size might not be uniform
  Usually assumed to be uniform and is considered good enough. Experimentation is required for more precise approximation.
• Not all functions (such as periodic, oscillating functions) can be compared

Asymptotic notation

A method used to categorize functions or to calculate upper/lower bounds with respect to the growth rate of functions. In this context, total number of steps followed by a specific algorithm is expressed in terms of its input size , then asymptotic analysis can be done.

Time complexity

Analysis of how the running time of the algorithm grows with various input sizes.

Instead of measuring the running time of the algorithm for specific inputs, how the running time increases with the increasing input size.

Space complexity

Analysis of additional space required for an algorithm to run.

Asymptotic functions

There are more than one asymptotic notations. All these are sets of functions.

Suppose are 2 functions of .

Big-O

iff :

An asymptotic upper bound.

Big-Omega

iff :

An asymptotic lower bound.

Big-Theta

iff :

An asymptotic equivalence. A tight characterization unlike Big-O or Big-Omega.

Soft-O

Denoted by . Similar to Big-O but the logarithmic terms are removed in the analysis. Not used as much as the other three.

Little-o

iff :

Strict upper bound characterization.

Implies Big-O.

Implies “not Big-Theta”.

Little-omega

iff :

Strict lower bound characterization.

Implies Big-Omega.

Implies “not Big-Theta”.

Limit definitions

Name	Definition
Little-o
Big-O
Big-Theta
Little-omega
Big-Omega

Properties of asymptotic functions

Transitivity

If and then . Applies to all 5 functions.

Reflexivity

Transpose

Relations between asymptotic notations

Big-O & Big-Omega

Big-Theta => Big-O & Big-Omega

Big-Theta equivalence

Real life timing

Wall-clock time

Time elapsed from start of the process to “now” when measured by a stopwatch.

User-cpu time

Time spent in user code.

System-cpu time

Time spent in kernel code.