A gentle introduction to asymptotic notation, complexity theory and algorithm runtime or space complexity classification
Angela Belfort, CEO of Firma Logistics strode into the meeting room quietly enraged. The way CEOs are enraged, composed and at the same time fuming. She is followed by her entourage. All the important people that make all the decisions. You’ve been at the company for just over a year and you’re not quite sure how you ended up in this room.
What you’ll learn
- Learn what the Big O notation is about.
- Look at an algorithm and classify it according to their Big O complexity.
- Identify and write more performant code and algorithms in your work as a software developer.
- Acquire the extra knowledge to help you pass more coding interviews.
- Exponential O(c^n), Quadratic O(n^2), Linear O(n), Log Linear O(n Log n), Logarithmic O(Log n) and Constant O(1) Complexity Functional Classes.
- Introduction to Complexity Theory.
Course Content
- Introduction –> 4 lectures • 23min.
- Linear Complexity Functional Class –> 3 lectures • 17min.
- Quadratic Complexity Functional Class –> 4 lectures • 36min.
- Constant Complexity Functional Class –> 3 lectures • 20min.
- Exponential Complexity Functional Class –> 3 lectures • 23min.
- Logarithmic Complexity Functional Class –> 3 lectures • 29min.
- Log Linear Complexity Functional Class –> 3 lectures • 19min.
Requirements
Angela Belfort, CEO of Firma Logistics strode into the meeting room quietly enraged. The way CEOs are enraged, composed and at the same time fuming. She is followed by her entourage. All the important people that make all the decisions. You’ve been at the company for just over a year and you’re not quite sure how you ended up in this room.
Her assistant had already set the room projector showing the live feed of the company’s fleet, over 4000 lorries scattered all over the country. Each vehicle was shown as a dot, colored red as stationary, green as moving. Almost all of them were red.
“What the hell is going on? I have lorry drivers complaining to unions because we aren’t able to give them a delivery schedule. I have furious suppliers on the lines asking for updates on their packages. We’ve got competitors circling over our clients like vultures. Can someone explain to me what is happening?”, Angela started.
Everyone was expecting an answer from the CTO, Brian Holms. Technically, on the huge org chart, he is your manager somewhere along the path from your position to the top, but it sure is a long way. He replies with “Er… em… We seem to be having some IT issues. I brought Alex here with me as she seems to have found a bug in the system”.
The focus is now completely on you. Hey, this might be the day you get fired after all… “It’s not really a bug. A section of the current scheduling algorithm has a quadratic runtime complexity with respect to the number of routes”.
The room looks at you as if you said the moon was made out of cheese. The big wigs turn their heads back to Brian for an explanation, but he seems as lost as they are. Instead he nervously nods, encouraging you to go on.
“Ok. Remember Paul Zimmer? Our ex-tech lead guy? Well it turns out that some of his old code does not scale well. It was fine while we had a few hundred lorries, but now that the company has grown so much the scheduling program is not able to keep up with the load. Especially on busy days like today. We have not really invested in keeping the code with the latest technologies and now nobody knows how it really works.” This is literally the most dumbed down version you can think of.
Angela jumps in “Where is this Paul?”
“He retired about a year ago. Rumor has it he opened an American diner in Hong Kong.”, replies Brian.
Angela’s composure is all gone now. “Can we fix the damn thing?”, she shouts.
“Well it’s very old code, nobody really understands how it works and we have been trying to reach Paul but if he’s in a different country… ”, puts in Brian but is interrupted by you.
“I already have a working linear solution. By linear I mean it will scale fine with our needs. I just need to run some further testing and then we can probably release it.”
Brian is visibly shocked. Everyone else is kind of confused, not completely sure what is going on. Angela is the only one with a grin.
Understanding the basics of Big O notation and being able to “read” how much an algorithm can scale is a must for all serious developers. This extra skill gives you the edge to take your career forward, to distinguish yourself from the rest of the crowd and get ahead. It helps you pass difficult coding interviews to get hired from some of the best tech companies.
The code in this course is in Python however if you have experience from any other major programming language (such as Java, C#, JavaScript, Ruby etc…) you’ll be ok with the code in the course as it’s designed to be easy to grasp.
All code in this course can be found on github, username/project: cutajarj/BigONotationInPlainEnglish
So don’t be a Brian, sign up to the course and learn something new today!