Introduction:

• Analyzing (calculating) time and space complexity is an important topic for interviews and competitive programming.
• Why its so important?
  • Performance Prediction:
    • Estimate execution time and memory usage before implementation.
  • Algorithm Comparison:
    • Choose the most efficient algorithm for large inputs.
  • Bottleneck Identification:
    • Detect operations or structures causing slowdowns.
  • Optimization Guidance:
    • Decide whether to trade time for space or vice versa.

Steps to Analyze Time Complexity:

• 1. Decide What to Analyze:

  • First, you decide whether you want to analyze best case, worst case or average case.
  • Reason: The number of operations (f(n)) may depend on this choice.
  • For Example:
    • Eg. 1 - Linear Search:
      • Best Case: Element is found at the first position.
      • Average Case: Element is found around the middle index.
      • Worst Case: Element is at the last position or not present at all.
    • Eg. 2 - Bubble Sort:
      • Best Case: Array is already sorted → Only one pass is needed.
      • Average Case: Elements are randomly arranged → Multiple passes required.
      • Worst Case: Array is sorted in reverse order → Maximum number of swaps and passes.

• 2. Calculate the Function Expression f(n):

  • We have already learned how to calculate function expression (f(n)) of the algorithm :
    • Click Here to read this topic deeply.
  • For Example:
    • Eg. 1 - Linear Search:
      • Function Expression f(n) for Best Case: f(n) = 3
      • Function Expression f(n) for Average Case: f(n) = (3n / 2) + 3
      • Function Expression f(n) for Worst Case: f(n) = 3n + 3
    • Eg. 2 - Bubble Sort:
      • Function Expression f(n) for Best Case: f(n) = 2n + 3
      • Function Expression f(n) for Average Case: f(n) = (3/2)n² + (3/2)n + 2
      • Function Expression f(n) for Worst Case: f(n) = (3/2)n² + (3/2)n + 2

• 3. Simplify f(n) using below rules:

  • Simplify the function expression f(n) using asymptotic notation rules (usually Big O notation).
    • Constant Work :   For eg. :   3   →   1
    • Drop Constant Terms (add/sub) :   For eg. :   n + 3   →   n
    • Drop Constant Multipliers (mult/div) :   For eg. :   3n   →   n
    • Drop Lower Order Terms :   For eg. :   n² + 3n + 2   →   n²
    • Logarithm Base Change → Ignore Base :   For eg. :   log₂ n   →   log n
    • etc...
  • For Example:
    • Eg. 1 - Linear Search:
      • Simplified f(n) for Best Case:
        • Constant Work :   →   3   →   1
      • Simplified f(n) for Average Case:
        • Drop All Constants :   →   (3n / 2) + 3   →   n
      • Simplified f(n) for Worst Case:
        • Drop All Constants :   →   3n + 3   →   n
    • Eg. 2 - Bubble Sort:
      • Simplified f(n) for Best Case:
        • Drop All Constants :   →   2n + 3   →   n
      • Simplified f(n) for Average Case:
        • Drop All Constants & Lower Order Terms :   →   (3/2)n² + (3/2)n + 2   →   n²
      • Simplified f(n) for Worst Case:
        • Drop All Constants & Lower Order Terms :   →   (3/2)n² + (3/2)n + 2   →   n²

• 4. State the Final Complexity

  • Write the result in Big-Omega (Ω) or or Big Theta (Θ) or Big-O (O) notation.
  • For Example:
    • Eg. 1 - Linear Search:
      • Best Case: Ω(1)
      • Average Case: Θ(n)
      • Worst Case: O(1)
    • Eg. 2 - Bubble Sort:
      • Best Case: Ω(n)
      • Average Case: Θ(n²)
      • Worst Case: O(n²)