Computational Complexity

Key Questions

• Time complexity: How much time is needed to finish?
• Space complexity: How much space is needed for computation?

Big O Notation

• Standard way to discuss the worst-case time and space requirements of an algorithm.
• Other notations: Big Theta (θ), Big Omega (Ω), etc.
• Focuses on the worst-case scenario.

Examples of Big O

• Linear Search:
  • Searching for a number in an unordered list.
  • Worst-case: Number is at the end.
  • Time complexity: Linear (O(n)).

Importance of Input Size (n)

• Big O becomes relevant as input size grows large.
• Constants and multiplicative factors are often ignored.

Common Big O Notation

• O(1): Constant time.
• O(log n): Logarithmic time.
• O(n): Linear time.
• O(n^2): Quadratic time.
• O(n^3): Cubic time.
• O(2^n), O(3^n), etc.: Exponential time.
• O(n!): Factorial time.
• Variations: O(√n), O(log log n), etc.

Properties of Big O

• Ignores constants and less dominant terms.
• Focuses on the most significant term as n approaches infinity.

Examples and Cases

1. Constant Time (O(1)):
   • Adding a constant, simple mathematical operations.
   • Loop fixed to non-n values.
2. Linear Time (O(n)):
   • Looping through all elements exactly once.
   • Slight variations (incrementing by a constant such as 3).
3. Quadratic Time (O(n^2)):
   • Nested loops iterating over elements multiple times.
   • Adjusting loop values to show complexity.
4. Logarithmic Time (O(log n)):
   • Binary search algorithm.
   • Cutting the input size by half every iteration.
5. More Complex Examples:
   • Multiple nested loops and how they contribute to overall complexity.
   • Various combinations of loop structures and their time complexities.

Classic Algorithms:

• Exponential (O(2^n)): Finding all subsets of a set.
• Factorial (O(n!)): Finding all permutations of a string.
• Merge Sort (O(n log n)): Efficient sorting algorithm.
• Nested Loops (O(n*m)): Iterating over a 2D array.