Algorithm Complexity: Time and Space

• Algorithmic complexity measures resources needed to solve a problem of a certain size.

Time Complexity

• Time complexity quantifies the time an algorithm requires for a problem of a specific size.
• Big O notation expresses time complexity, indicating the upper limit of the algorithm's runtime growth as input increases.
• Examples of time complexities:
  • $O(1)$: Constant time
  • $O(log n)$: Logarithmic time
  • $O(n)$: Linear time
  • $O(n log n)$: Linearithmic time
  • $O(n^2)$: Quadratic time
  • $O(2^n)$: Exponential time
  • $O(n!)$: Factorial time

Space Complexity

• Space complexity assesses memory an algorithm needs for a problem of a given size.
• Big O notation is used to denote space complexity, defining the upper growth limit of an algorithm's memory usage as the input grows.

Example Algorithm Analysis

• Consider a sorting algorithm:

for i from 1 to n:
    for j from i+1 to n:
        if arr[i] > arr[j]:
            swap arr[i] and arr[j]

• Time Complexity: The nested loops result in $n(n-1)/2$ iterations, making it $O(n^2)$.
• Space Complexity: The algorithm uses a constant amount of extra memory, resulting in $O(1)$ space complexity.

Common Time Complexities

Diagram of Time Complexities

• A log-log plot visualizes time complexity versus input size $n$.
• The x-axis represents Input Size ($n$) from 1 to 100.
• The y-axis represents Time Complexity from 1 to $10^8$.
• The graph illustrates several time complexities:
  • Constant ($O(1)$): Displayed as a horizontal line at Time Complexity = 1.
  • Logarithmic ($O(log n)$): Increases slowly as $n$ increases.
  • Linear ($O(n)$): Shown as a straight line with a slope of 1.
  • n Log n ($O(n log n)$): Increases faster than linear.
  • Quadratic ($O(n^2)$): Increases much faster than linear.
  • Exponential ($O(2^n)$): Increases extremely rapidly.