Summary of "Time and Space Complexity - Strivers A2Z DSA Course"
Summary of "Time and Space Complexity - Strivers A2Z DSA Course"
This video lecture from Striver’s A2Z DSA Course introduces the fundamental concepts of Time Complexity and Space Complexity, focusing on their importance in coding interviews and how to analyze them practically.
Main Ideas and Concepts
1. What is Time Complexity?
- Time Complexity measures the rate at which the time taken by a program increases with respect to input size, not the actual time taken in seconds or milliseconds.
- Actual run time depends on hardware and environment, so it is not a reliable measure.
- Time Complexity is expressed using Big O notation which abstracts away constants and lower order terms to focus on growth trends.
2. Why Time Complexity is Important
- Interviewers judge code efficiency based on Time Complexity, not actual runtime.
- Helps in understanding how scalable your code is with increasing input size.
3. How to Compute Time Complexity
- Count the number of operations or iterations in your code.
- Use Big O notation to express this count in terms of input size (e.g., O(n), O(n²)).
- Avoid counting every single step manually; instead, use rules and patterns.
4. Three Important Rules When Computing Time Complexity
- Always consider the worst-case scenario (upper bound).
- Ignore constants because they become insignificant for large inputs.
- Ignore lower order terms since they have minimal impact on growth rate.
5. Best Case, Average Case, Worst Case
- Best case: minimum number of operations (e.g., input that triggers earliest exit).
- Worst case: maximum number of operations (used for analysis).
- Average case: average of best and worst cases.
- Interviews usually focus on worst-case complexity for robustness.
6. Big O notation
- Expresses the upper bound of Time Complexity.
- Examples:
- A simple loop running n times → O(n)
- Nested loops running n times each → O(n²)
- Summations of loops can be simplified using arithmetic series formulas and then reduced by ignoring constants.
7. Other Notations (Briefly Mentioned)
- Theta (Θ): tight bound (both upper and lower).
- Omega (Ω): lower bound (best case).
- These are mostly theoretical and rarely asked in interviews.
Examples and Methodologies
- Simple for loop example:
for (int i = 1; i < n; i++) {
cout << "Raj";
}
Time Complexity: O(n) because it runs n times.
- Nested loops example:
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
// constant time operation
}
}
Time Complexity: O(n²) because inner loop runs n times for each iteration of outer loop.
- Triangular nested loop example:
for (int i = 0; i < n; i++) {
for (int j = 0; j <= i; j++) {
// constant time operation
}
}
Time Complexity: O(n²), derived from sum of first n natural numbers: n(n+1)/2.
Space Complexity
- Space Complexity measures the amount of memory used by the program relative to input size.
- Expressed similarly in Big O notation.
- Defined as:
- Auxiliary space: extra space used by the algorithm (e.g., temporary variables, arrays).
- Input space: space required to store input data.
- Example:
- Using three variables → O(1) space.
- Using an array of size n → O(n) space.
- Important practice: Do not modify the input data directly (e.g., do not overwrite input arrays or variables). Always use extra space if needed to avoid altering input, as this is considered a bad practice in software engineering and interviews.
Practical Tips for Competitive Programming
- Servers typically allow about 108 operations per second.
- If a problem has a time limit of 1 second, aim for code with Time Complexity roughly O(108) operations or better.
- Avoid overestimating allowed operations (e.g., don’t assume 1016 operations in 1 second).
Summary of Methodology to Analyze Time Complexity
- Identify loops and nested loops.
- Calculate total iterations (multiplying loop counts).
- Use arithmetic series formulas for nested loops with dependent limits.
- Ignore constants and lower order terms.
- Always consider the worst-case scenario.
- Express the final complexity in Big O notation.
Summary of Methodology to Analyze Space
Category
Educational
