πŸŽ‰ 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:
    • Decide which case you are analyzing:
      • Best Case β†’ Minimum time the algorithm can take.
      • Average Case β†’ Expected time over all inputs.
      • Worst Case β†’ Maximum time the algorithm can take. (mostly asked in interviews)
    • Choose the input size variable (usually n) and the unit of measurement (e.g., count of operations, comparisons or basic steps).
    • 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 Function Expression f(n) of the Algorithm:
    • 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 Asymptotic Notation 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Β²)