High Level Big-O Notation => Time Complexity
If you’re learning programming or software development, you’ve probably ran into topics such as data structures, time complexities, space complexities, and algorithms. Truth be told, these topics aren’t really taught in web development bootcamps and it’s up to you to study up on them. That’s why today, we’re going to be going over the importance of Big-O and why you should have at least some knowledge on it.
Why is this knowledge important?
Big-O notation can simply be summed up as how “efficient” you’re algorithms run. That’s a very loose summation, but it’s important in the job of software engineering/development and interviews. The latter is what I’ll make a point on. Say you’ve landed a technical assessment interview, solved the algorithm challenge, and passed all the test cases. Now the interviewer may ask you “what’s the time complexity and can you make it better?” Uh oh. Solutions are good but being able to improve efficiency is even better! Take a look at the graph below to get a high level understanding of various time complexities. We’ll get into space complexity a bit later.
As you can see, O(1) is the best case in time complexity. Time complexity isn’t necessarily how fast an algorithm will run, but how the algorithm will react given varying dataset sizes. For example, O(1) or otherwise know as “constant” essentially means that the same amount of steps will execute no matter the size of your dataset. This is the best case scenario for time complexity, because you can ensure that execution time is constant whether you have a dataset of 5, or a 100,000+. As you go up/increase in time complexities to let’s say O(n²), the execution steps is exponentially higher in relation to your dataset.
Example and why this pertains to data structures?
Let’s use a relatively easy data structure that we often use. An array contains a list of “something”, whether that be integers, strings, objects, or even nested arrays/objects. For simplicity sake, we have an arrayOfNum which contains the integers [1, 8, 3, 41, 5]. Now imagine if we have to traverse the array for whatever reason. We will be visiting each integer or index and that is dependent on the size of the array. This would equate to O(N) time complexity because in our example, we will have 5 steps. In a different example with let’s say 1,000 integers, we will have 1,000 steps. To simplify this we say “O of N” to indicate that the steps will be the same as the size or “n” length of the array. I would highly suggest looking up the lookup time of each of the different data structures to be ready in case it’s asked in an interview. The purpose of this blog is for a simple introduction into Big-O notation with time complexity. I’ll be writing about space complexity and in the next blog which involves bits and bytes. Hopefully you’ve found this helpful and stay tuned!