Algorithm: Big O Notation

Overview

The Big O Notation generally describes how efficient an algorithm is. Specifically, it measures how long an algorithm takes to execute, under the worst case scenario.

Statements

Given a sequence of statements

statement 1
statement 2
...
statement k

If we assume each statement are constant time operations, then the total time for running the above set of statements are as follows:

total time = time(statement 1) + time(statement 2) + ... + time(statement 3)

Conditions

When presented an if-elif-else statement,

if (condition 1): block 1 (sequence of statements)
elif (condition 2): block 2 (sequence of statements)
else: block 3 (sequence of statements)

the worst-case time, is the slowest of the three possibilities.

max(time(block 1), time(block 2), time(block3))

Algorithm Times

Constant Time O(1)

An algorithm is referred to constant time, if it executes in the same amount of time regardless of the input value provided.

## check_int: check if supplied value is an integer type.
def check_int(value):
  return isinstance(value, int)

Linear Time O(n)

An algorithm is referred to linear time, if the time it takes to execute, is directly proportional to the input value size.

## print_range: print values within the supplied 'value' range.
def print_range(value):
  for x in range(value):
    print x

Quadratic Time O(n^2)

An algorithm is referred to quadratic time, if the time it takes to execute, is directly proportional to the squared input value size.

## print_nested_range: print values within the supplied 'value' range.
def print_nested_range(value):
  for x in range(value):
    for y in range(value):
      print x, y

Note: the above example, the range(value) were identical for both loops. Instead, if we had z number of nested loops, with the same range(value), then the algorithm time would be zth power. However, if the above example had different range(value), then the algorithm time be O(N * M).

Exponential Time O(a^n)

An algorithm is referred to exponential time, if the time it takes to execute, is exponentially proportional to the input value size. Therefore, with increase input value size, the runtime increases by a factor of a, where a > 1.

The following is O(2^n) exponential time:

## fibonacci: return the nth fibonacci number.
def fibonacci(value):
  if value == 0: return 0
  elif value == 1: return 1
  else: return fibonacci(value - 1) + fibonacci(value - 2)