Big O/ Space/Time Complexity

• Time complexity:

  • How the times scales as data size increases

  Space complexity:

  • The amount of memory(resources) required
• Finding the complexity of an algorithm:

  • Rule 1: Remove all terms apart from the one with the largest exponent or factor
  • Rule 2: Remove any constants
• O(1) complexity:

  • Constant complexity, no matter the size of the input, the execution time will always be the same
  • If there are no loops it probably has O(1) complexity

  
• O(log n) complexity:

  • Logarithmic complexity, the impact of the algorithm is directly proportional to the logarithmic result of the input size
  • If you are halving a data set then it has O(log n) complexity
  • the rate of increase gets smaller as the amount of data increases
• O(n) complexity:

  • Algorithm's execution time increases in proportion to amount of elements(inputs)
  • If there is a single loop the complexity is probably this O(n)
• O(n^2) complexity:

  • Polynomial complexity, the impact of the algorithm is directly proportional to the square of the number of elements
  • If there are 2 nested loops
• O(2^n) complexity:

  • The algorithm execution time will double each with each additional item in the input
  • This is the time complexity for a recursive function that calls itself twice
• Complexities of all searching algorithms:

  Best case scenario for all of them is O(1)

  Linear:

  • Average - O(n)
  • Worst - O(n)

  Binary search array:

  • Average - O(log n )
  • Worst - O(log n)

  Binary search tree:

  • Average - O(log n )
  • Worst - O(n)

  Hashing

  • Average - O(1)
  • Worst - O(n)

  Bread/depth first:

  • Average - O(Vertices+Edges)
  • Worst case - O(Vertices^2)
• Complexities of sorting algorithms:

  Note bubble and insertion exactly the same

  Bubble sort:

  • Best - O(n)
  • Average - O(n^2)
  • Worst - O(n^2)
  • Space complexity - O(1)

  Insertion Sort:

  • Best - O(n)
  • Average - O(n^2)
  • Worst - O(n^2)
  • Space complexity - O(1)
• Complexities of sorting algorithms:

  Merge sort:

  • Best/ Average/ Worst - O(n log n)
  • Space complexity - O(n)

  Quick sort:

  • Best -O(n log n)
  • Average -O(n log n)
  • Worst - O(n^2)
  • Space complexity - O(log n)
• Purpose of the Big O notation:

  • Evaluate the complexity of the algorithm
  • Evaluate worst case scenario for the algorithm
  • measures the number of steps and memory usage change according to the data as the amount of data being processed increases