🎉 Festival Deal: Save Big on Professional Courses with Real Projects – Apply Coupons FEST300OFF FEST500OFF
→ Click Here ←

How to Analyze Time and Space Complexity
of an Algorithm  


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 :
    • 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   →  
        • Simplified f(n) for Worst Case:
          • Drop All Constants & Lower Order Terms :   →   (3/2)n² + (3/2)n + 2   →  
  • 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²)