Overview
This lecture covers the basics of time complexity and space complexity in algorithms, focusing on their definitions, how to compute them, and best practices for interviews.
Time Complexity Fundamentals
- Time complexity measures how the runtime of an algorithm increases with input size, not the actual time taken.
- It is independent of the system or hardware used to run the code.
- Time complexity is expressed using Big O notation (e.g., O(n)), not in seconds or minutes.
- The rate at which time grows with input size determines the time complexity.
Big O Notation & Calculation Rules
- Use Big O notation to describe the upper bound (worst case) of algorithm performance.
- Always compute time complexity based on the worst case scenario, not best or average cases.
- Avoid including constants and lower-order terms when expressing Big O; e.g., O(3n) simplifies to O(n).
- For nested loops, multiply the number of iterations; e.g., two nested loops from 0 to n result in O(n²).
- For incremental loop sums (e.g., i from 0 to n-1, j from 0 to i), the total is O(n²) after simplification.
Best, Average, and Worst Case
- Best case: minimum operations needed (e.g., first condition met).
- Worst case: maximum operations (e.g., last condition or full loop).
- Average case: average operations between best and worst, but interviews usually focus on worst case.
Constants and Lower-Order Terms
- Ignore small constants or lower-order terms for large input sizes; they have negligible impact.
- For expressions like 4n³ + 3n² + 8, focus on the highest degree term: O(n³).
- Do not manipulate input data directly in interviews; use extra variables if needed.
Space Complexity Fundamentals
- Space complexity refers to total memory used by an algorithm, typically expressed as O(<variable count or size>).
- Space complexity = auxiliary space (extra variables) + input space (input storage).
- Avoid modifying input data; always use new variables to preserve data integrity.
Competitive Programming Tips
- Most servers process about 10⁸ operations per second.
- When a problem sets a time limit of 1 second, ensure your solution's time complexity is ≤ O(10⁸) operations.
Key Terms & Definitions
- Time Complexity — The rate at which algorithm execution time increases as input size increases.
- Big O Notation — A notation to describe the worst-case upper bound of algorithm complexity.
- Auxiliary Space — Additional memory used by an algorithm, excluding input storage.
- Input Space — Memory required to store the input data.
- Best/Average/Worst Case — Scenarios describing minimum, average, and maximum operations an algorithm might need.
Action Items / Next Steps
- Practice analyzing time complexity for different code snippets using Big O notation.
- Review upcoming lecture materials on pattern-based nested loop analysis.
- Avoid manipulating input data directly in future coding exercises.