Algorithm: Big O Notation

Overview

The Big O Notation generally describes how efficient an algorithm is. Specifically, it measures the worst case scenario of an algorithm.

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

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)