Algorithmic Complexity: Time and Space

• Algorithmic complexity measures the resources an algorithm needs based on input size.
• Big O notation is used to express the upper bound of resource usage growth rate.

Time Complexity

• Time complexity measures the time an algorithm takes as a function of input size.
• Measured by the number of elementary operations.
• Common complexities:
  • O(1): Constant time.
    • Same time regardless of input size.
  • O(log n): Logarithmic time.
    • Time increases logarithmically with input size.
  • O(n): Linear time.
    • Time increases linearly with input size.
  • O(n log n): Linearithmic time.
    • Time increases linearly with input size, multiplied by a logarithmic factor.
  • O(n^2 ): Quadratic time.
    • Time increases quadratically with input size.
  • O(2^n ): Exponential time.
    • Time increases exponentially with input size.
  • O(n!): Factorial time.
    • Time increases factorially with input size.

Space Complexity

• Space complexity measures the memory an algorithm needs as a function of input size.
• Measured by number of variables or data structures used.
• Common complexities:
  • O(1): Constant space.
    • Same memory regardless of input size.
  • O(log n): Logarithmic space.
    • Memory increases logarithmically with input size.
  • O(n): Linear space.
    • Memory increases linearly with input size.
  • O(n^2 ): Quadratic space.
    • Memory increases quadratically with input size.

Big O Notation

• This is a mathematical notation describing a function's limiting behavior.
• It is used to classify algorithms by running time or space requirement growth as input size grows.
• Formal Definition:
  • f(n) ≤ c·g(n) for all n ≥ n0
  • f(n) is O(g(n)) if f(n) grows no faster than g(n) as n approaches infinity.
  • Example:
    • Expression 4n^2 + 6n - 5 is O(n^2)

Best, Average, and Worst-Case Complexity

• Best-Case: Algorithm complexity with most favorable input.
• Average-Case: Algorithm complexity averaged over inputs.
• Worst-Case: Algorithm complexity with least favorable input, provides an upper bound on resource usage and most commonly used.

Analyzing Algorithm Complexity

• Steps:
  • Identify elementary operations.
  • Determine how many times each is executed as a function of input size.
  • Express total operations using Big O notation.

Examples

Linear Search

• Searches for a value in an unsorted array.
• Time Complexity: O(n) in the worst case.
• Space Complexity: O(1).

Binary Search

• Searches for a value in a sorted array.
• Time Complexity: O(log n).
• Space Complexity: O(1).

Bubble Sort

• Sorts an array by repeatedly comparing and swapping adjacent elements.
• Time Complexity: O(n^2).
• Space Complexity: O(1).

Conclusion

• Understanding algorithmic complexity is essential for designing efficient algorithms.
• Analyze time and space complexity to make informed decisions for best performance.