What is time complexity?

  • It is the measure of how long an algorithm will run as the size of the input increases–this examines the proportional time of the largest components of the algorithm.

    • Proportional Time: Only being mindful of the running-time of an input of size n, NOT the running-time for a specific input.
    • Example:
    int sum{};
for( const auto i : arr )
  if( num % 2 == 0 )
    sum += num;

return sum;

    Note: In this example, the loop will iterate the entire array once, so it runs directly proportional to n (linear run time).

  • Time complexity only cares about the numbers that change in proportion to the input size, NOT the running time of the input. TLDR; input size > running time

Types of Running Time

Imagine a scenario where an algorithm needs to look for a number in a list by searching through the list linearly.

  1. Worst-case Running Time
  • The algorithm iterates through the entire list and doesn’t find the number it is looking for. It took the algorithm linear time to do so.
  1. Best-case Running Time
  • The algorithm iterates through the entire list but is lucky to find the number in its first check. It took the algorithm constant time to do so.
  1. Expected-case Running Time
  • The algorithm finds the number halfway through the list.

What is Big-O?

  • It is used to classify the time complexity of algorithms.
  • Types of Big-O Categories (starting from fastest to slowest):
    1. O(1) - Constant Time
    2. O(log n) - Logarithmic Time
    3. O(n) - Linear Time
    4. O(n log n) - Linearithmic Time
    5. O(n^2) - Quadratic Time
    6. O(2^n) - Exponential Time
    7. O(n!) - Factorial Time

O(1) - Constant Time

  • Algorithm performs a constant number of operations regardless of the size of the input (remember, size > running time).
  • Examples
    1. You obtain data from an array via index.
    2. You use a key to obtain the value from a dictionary.

O(log n) - Logarithmic Time

  • As input size increases, the running time grows by log(n).
  • Growth rate for log time are relatively slow, and O(log n) algorithms are usually fast.
  • Examples
    1. Binary search on a sorted list. Size of the sorted list will be split in half each time until the element is found or there is one element left. ( When the size of n is 1 billion, log(n) is 30; When n is 100, log(n) is 7).
    2. Balanced Binary Searched Tree. The left child of a node is less than the parent and the right child is greater than the parent. Will either go left or right to eliminate half of the whole tree to find the number that it is looking for.

To get the number of potential ways to eliminate numbers of an O(log n) algorithm, just keep dividing by 2 until the number is below 1.