Algorithm Analysis and Big O Notation

• Algorithm analysis defines the process of determining the resources needed to execute an algorithm.
• Time complexity measures the time an algorithm takes relative to input size.
• Space complexity measures the memory space an algorithm requires relative to input size.
• Big O notation provides an upper bound on the growth rate of an algorithm's resource usage.

Big O Notation

• Big O notation classifies algorithms by how their runtime or space needs grow with input size.
• $O(f(n))$ defines functions that grow no faster than $f(n)$, where $n$ is the input size.
• $O(1)$ indicates constant time complexity, where execution time is independent of input size.
• $O(\log n)$ indicates logarithmic time complexity, where execution time increases logarithmically with input size.
• $O(n)$ indicates linear time complexity, where execution time increases linearly with input size.
• $O(n \log n)$ indicates log-linear time complexity, more efficient than quadratic.
• $O(n^2)$ indicates quadratic time complexity, where execution time increases quadratically with input size.
• $O(2^n)$ indicates exponential time complexity, where execution time doubles with each input element.
• $O(n!)$ indicates factorial time complexity, where execution time increases factorially with input size.

Common Complexities

Example 1: Constant Time Complexity

• The time complexity of the get_first_element function is $O(1)$.

def get_first_element(arr):
  return arr

Example 2: Linear Time Complexity

• The time complexity of the search_element function is $O(n)$.

def search_element(arr, target):
  for element in arr:
    if element == target:
      return True
  return False

Example 3: Quadratic Time Complexity

• The time complexity of the bubble_sort function is $O(n^2)$ due to nested loops.

def bubble_sort(arr):
  n = len(arr)
  for i in range(n):
    for j in range(n - i - 1):
      if arr[j] > arr[j + 1]:
        arr[j], arr[j + 1] = arr[j + 1], arr[j]