Lecture Notes: Time Complexity and Space Complexity

Introduction

• Continuation of Strivers A to Z DSA course.
• Focus on time complexity.
• Importance of time complexity in interviews.

What is Time Complexity?

• Definition: The rate at which the time taken by an algorithm increases with respect to the input size.
• Not Equal to Time Taken: It's independent of the machine and its configuration.
• Importance in Interviews: Interviewers judge your code based on its time complexity and space complexity.

Computing Time Complexity

• Big O Notation: Used to express time complexity.
  • Form: O(some_function_of_input_size) e.g., O(n).
  • Example: For a loop running n times, it's O(n), for a nested loop running n*n times, it's O(n^2).
• Steps in the Code: Count the steps in terms of loops and operations.*

Rules to Compute Time Complexity

1. Worst-Case Scenario: Always consider the worst-case for computation.
2. Avoid Constants: Ignore constant factors in the computation.
3. Avoid Lower Values: Ignore lower-order terms for large input sizes.

Best, Worst, and Average Case

• Best Case: Minimum time an algorithm takes, e.g., first statement condition in an if-else ladder is true.
• Worst Case: Maximum time taken, e.g., the last condition in if-else ladder is true.
• Average Case: (Best Case + Worst Case) / 2.

Examples of Time Complexity Calculations

• Nested loops: the outer loop runs n times, and the inner loop runs n times, resulting in O(n^2).
• Single loop: running n times results in O(n).
• Avoid constants and lower values to simplify calculations.

Space Complexity

• Definition: The memory space that an algorithm uses.
• Components: Auxiliary space + Input space.
  • Auxiliary Space: Extra space used to solve the problem.
  • Input Space: Space used to store the input values.
• Big O Notation for Space: Similar to time complexity, expressed in terms of O(some_function). E.g., an array of size n uses O(n) space.
• Best Practices: Avoid altering the input data, use extra variables or arrays if necessary.

Competitive Programming Tip

• Time Complexity Assessment: Most servers allow 10^8 operations per second, so design algorithms accordingly.

Conclusion

• Overview of time complexity and space complexity basics.
• Next steps include solving patterns with nested loops and further time complexity analysis.
• Encourage continuous learning and practicing code with time and space complexity in mind.

Reminder

• For in-depth discussion and better understanding, follow the playlist and upcoming lectures on nested loops and pattern problems.