Embedded Files
- What are these?
Time Complexity of an algorithm or piece of code is the time taken for it to complete its operation as a function of its data input size, n.
Space Complexity of an algorithm or piece of code is the amount of memory needed for its operation as a function of its data input size, n.
2. Why should you know time and space complexities?
2. Why should you know time and space complexities?
It helps you compare solutions/algorithms and pick the better one.
Time and space complexities are some of the most popular questions asked in DSA interviews, since these are a sure shot way to understand if the candidate has understood a problem or not.
In coding problems, there are constraints based on time and space, so that you're forced to use time/space optimal solutions. For instance, you cannot use three nested loops when n is given to be around 10^4, because otherwise, your code would not pass some test cases.
3. Introduction to time complexity of algorithms
3. Introduction to time complexity of algorithms
A short introduction to what is time complexity, and the time complexity of common algorithms.
Who should see this : Those who are new to the concept of time complexities
Who should read this : Those who want to understand the relation between code and time complexities with a few simple code samples.
This is a very detailed and expansive content piece on the TCs of common algorithms. It is accompanied by several videos and code snippets. The ideal way to use this resource would be to read through the concepts once, and bookmark it for reference as well.
Note that you do not need to have all the TCs by heart - once you have a fair idea of the patterns, you will be able to easily guess/calculate TCs - it takes time and practice.
Here is a list of some standard problems to understand the time and space complexities of those.
You can try to answer these to test your understanding of time and space complexity.
7. Some tips
7. Some tips
Make it a point to understand and not just learn time complexities of the problems you solve, since there are chances that you may not get the same problem again in interviews.
Identify and understand common patterns to easily figure out TCs. Example - TC of algorithms where for loop generally moves as i = i*2 is O(log n) base 2.
In most compilers, complexity of algorithm more than 10^9 would result in TLE(Time Limit Exceeded) error. Thus, if N is given to be around 10^5, you should not use an O(N^2) solution. Since O(10^5^2) = O(10^10), which would give TLE.
Who should view this : Those who wish to gain a visualization of time complexity, of wish to quickly refer to TCs of common algorithms. This sheet can be used as a cheat sheet before an interview, or to gain a bird's eye view of the common TCs.
Some additional references
Some additional references
Who should view this : If you wish to understand/practice more on TC/SC.
Page updated
Report abuse