Step 1: Understanding Time Complexity
Time complexity is a measure of the time an algorithm takes to complete as a function of the length of the input.
Analogy
Think of time complexity like preparing a meal. The more ingredients (input size) you have, the more time it might take to prepare the meal (algorithm execution).
Example in Python
Consider a simple linear search:
def linear_search(arr, x):
for i in range(len(arr)):
if arr[i] == x:
return i
return -1
Time Complexity: O(n) – As the size of the array arr
increases, the time to search increases linearly.
Step 2: Understanding Space Complexity
Space complexity is a measure of the amount of memory space an algorithm uses in relation to the length of the input.
Analogy
Think of space complexity as the number of pots and pans you use to cook a meal. More complex meals (algorithms) might require more kitchenware (memory).
Example in Python
Consider an algorithm that stores intermediate results in a list:
def calculate_squares(n):
squares = []
for i in range(n):
squares.append(i * i)
return squares
Space Complexity: O(n) – The space needed grows linearly with the input n
.
Step 3: Calculating Time Complexity
- Identify the Basic Operations: In your code, look for loops, recursive calls, and other operations that change with input size.
- Count the Operations: Estimate how many times these operations are executed in terms of input size.
- Formulate Time Complexity: Express the number of operations in Big O notation (e.g., O(n), O(log n), O(n^2)).
Step 4: Calculating Space Complexity
- Consider Variables and Data Structures: Note all the variables and data structures used in the algorithm.
- Count the Memory Usage: Estimate how the memory usage scales with input size.
- Formulate Space Complexity: Express this in Big O notation.
Step 5: Consider Worst, Average, and Best Cases
- Worst Case: The maximum time or space the algorithm will take.
- Average Case: The expected time or space for a typical input.
- Best Case: The minimum time or space for the most favorable input.
Example: Calculating Time Complexity
Consider a simple for loop:
for i in range(n):
print(i)
- Basic Operation: The print statement.
- Count the Operations: It runs
n
times. - Time Complexity: O(n).
Example: Calculating Space Complexity
Consider an algorithm that creates a new list:
new_list = [i for i in range(n)]
- Variables/Data Structures: One list of size
n
. - Count the Memory Usage: It grows linearly with
n
. - Space Complexity: O(n).
Conclusion
To effectively calculate time and space complexity, understand the operations your algorithm performs, how they scale with input size, and express them in Big O notation. Remember, complexity analysis helps in predicting algorithm efficiency and resource usage, making it a cornerstone of algorithm design and optimization.
Hello, I’m Anuj. I make and teach software.
My website is free of advertisements, affiliate links, tracking or analytics, sponsored posts, and paywalls.
Follow me on LinkedIn, X (twitter) to get timely updates when I post new articles.
My students are the reason this website exists. ❤️
Clear lessons, easy to follow even for a beginner. Very knowledgeable and gives great encouragement to beginner coders. Really helpful and responded to questions quickly. No problem too big or too small. Friendly teaching style meant I didn’t feel embarrassed to ask silly questions.
Louise
I like your jokes. It was always nice how you made us giggle sometimes. Your responsiveness was super appreciated and i loved the additional resources. I think it was nice that you spoke slowly and clearly
Elizaveta
First, Anuj makes efforts to simplify explanations of a concept and gives practical examples in a structured way. Second, he doesn’t just teach us things. He takes time to listen to our concerns and motivates us by sharing his personal experience and thoughts as an experienced software engineer.
Amanda Kartikasari
The presentations you prepare yourself are much more information dense, available and I found some topics are much easier to grasp using them, so grateful for the extra materials you always provide.
Asya Seagrave
Very thorough in terms of showing how to get the code to initially work and what the different errors could be, as well as how to fix them. Very efficient teaching style!
Cerys Cullen
Really liked your teaching style, always very clear and you explained things nice and simply which was great when learning a brand new topic! Loved your videos which were concise, easy to follow and super helpful for going back over to practice with. Loved all the extra resources you provided, your blog, and just in general how helpful and passionate you are about what you do! Thank you so much!
Megan Bradley
Anuj was a clear and concise instructor, who was always happy to help no matter the timing of it. I also liked that he made everyone feel welcome and fostered an inclusive culture, which made our team not afraid to present even if we were slightly unsure if our project work would live up the the standard of the rest of the group.
Deni Hancox
The style of the learning structure has been very constructive and the availabilityof the instructor helps to build confidence and security to try, fail and learn. 5 stars to the instructor style!
Maryl Duprat
Anuj was a fantastic instructor, super informative and knowledgeable. He was very approachable with questions, and clear and concise in his explanations. 🙂
Alice Pinch
Anuj is a great instructor who is very knowledgeable and passionate about what he teaches. He worked well with his co-instructor, which led to a positive learning experience. The course itself is an introductory course but still has a lot of material to cover, but Anuj was very meticulous in explaining concepts to ensure lessons were executed and understood. He is a great listener and always willing to answer questions no matter how obvious (and sometimes silly). I have already signed up for another course and am hoping he will be part of the team!
Pam
Well-structured lessons with the use of diagrams/images to help students understand concepts. Demonstrated examples step-by-step and answered any queries students had.
Maria
Anuj is a great instructor, who was incredibly dedicated to the course, both during teaching hours and after them. I really enjoyed the fun material he posted after the sessions, such as games and fun facts on our Slack channel. I highly appreciate that he was always responsive and patient with any queries or questions that I had, and so any confusions were very temporary.
Raimunda Bukartaite
Really engaging and helpful, always happy to answer any questions I had!
Muskaan
I really liked that the classes involved solving problems during the class and it wasn’t a person speaking alone all the time. I really appreciated the support and commitment of the instructors during the whole course.
Victoria Caballero
Instructions were really clear, and Anuj was very encouraging. He was always open to answering questions and very patient with the class.
Rashida Adekunle
Clear instructions and useful coding habits highlighted.
Asnath Lubanza
Always very helpful – going an extra mile to aid students. Always welcomes questions and will not make you feel bad or stupid for asking.
Maria
Patient when teaching, explains everything clearly and simply for non-techies(!), willing to go slower if us students find it fast or hard to keep up or understand, willing to go over topics and ensure everyone understands. Anuj goes above and beyond for the students despite understanding and learning differences. Outside of class and after class – a passionate and great teacher.
Ameera
Really enjoyed coding alongside you, clear and concise instructions and even some bits that were necessarily on the slides, but were SUPER helpful to us and our understanding of the language
Francessca
Very informative, supportive and friendly. The latter made you very approachable so I felt more at ease asking for help with things.
Amy Mulligan
I found the use cases made things very easy to follow and understand – when I was learning by myself, I was confused at some of the concepts because I couldn’t see how they would be applied, whereas you gave real-life examples that really helped it slot together!
Anastasija Medvedeva
Very supportive, very clear and gives great demonstrations and examples. The extra slides and YouTube videos were also a huge help for me.
Daisy Dobson
I liked that you walked through what you were writing for the code and showed different expamples for the same concept
Fabiha Chowdhury
Used relevant examples of code in the real world, and took the time to explain difficult ideas.
Chloe
I like you are very helpful and teaching the things again and again and make people comfortable to ask you a questions.
Pinar Seker
I think you taught everything really well, thank you! All questions you answered concisely and shared lots of resources.
Ria Kakkad
Your words were organize, not chaotic. You know how to pass the knowledge to students. Thank you
JL
Very clear speaker. Passionate about what you are speaking about. Add your own knowledge into the classes and don’t just read from the script/slides. Explain things in an easy to understand manner. Always available to help.
Caroline Bell
Great teacher, extremely helpful and taught the course in a way which was understandable
Emma McKinney
I liked it, it was very helpful with the tips and notes, also the knowledge was definitely evident so was trustworthy and made me feel comfortable when I thought I asked a stupid question and always had help available.
Sermin Efendi
Really clear, concise and supportive. Broke down complicated problems easily with other examples. The extra content you created with your slides were incredibly helpful.
Nalani St Louis
lots of personality and availability to answer questions/doubts
Liyaan Khoso
Everything Anuj! As a teacher myself, I loved learning from you. You were so patient with us and answered every question we asked so well. You also had a way of making difficult things seem easy. Your passion and dedication showed.
Onyeoma Adigwe
very structured and easy to follow. Very supportive with all the students and always giving insightful advices.
Miriem Shaimi
I really like how you try to simplify and give real-life analogies to coding concepts. Really grateful for all the support you give to us students, especially by addressing our questions and for being available when we are lost. Really grateful for it as it shows how much you care for your students.