Big O Notation
Big O Notation is commonly referred to by many software engineers. The importance of knowing the knowledge behind Big O Notation is significantly high as you come across bigger databases. You won’t see a significant amount of problems with smaller data sets, but as you progress to build more complex data sets, it’s important to know how the Big O Notation works.
What is Big O Notation?
Big O Notation is a mathematical notation that is used to calculate runtime efficiency. Of course this is in respect to input variables, and the Big O Notation can be a huge help to tackle those situations where your program can be running very slowly.
The runtime grows due to certain algorithms that are being used in the programs that are executed. Our very own software is heavily based on an immense amount of data. Using this data for our own personal needs is what coding is all about. In computer science we use sorting algorithms to sort this data in a logical order. You can sort data in many different ways and you can be creative with it (there’s no wrong answer in how you choose to sort your data). Sorting algorithms is what makes our life easier as software engineers, and each sorting algorithm has different approaches, but get to the same or similar results.
Examples of sorting algorithms are Bubble Sort, Quick Sort, Selection Sort, Merge Sort, Heap Sort, etc. Sorting algorithms are important because if someone wanted to access a list of information, we don’t want it to be scattered in this whole big nest of data. In terms of efficiency, sorting algorithms does the job of making our data neat and precise, making it easier to access. Neater data equals higher efficiency.
The way we determine how quickly the runtime grows in Big O Notation is by the size of the input, which we call “n”. There are different scales of “n” in which the Big O Notation refers to. Examples of these scales are O(n) or (O(n²)). The O is referring to the growth rate, and the “n” is the length of the array that needs to be sorted.
When i was in college my professor told me a story of how every software engineer that worked for him would print out this sheet of the Big O Notation and tape it onto their desk. It comes in handy especially when you come across a situation where you can mathematically understand why a certain sorting algorithm wouldn’t suit best for that specific job.
This chart really explains the complexity of the Big O Notation and makes it a lot more simple through a visual representation. To break down this chart it goes back to what was said before, it goes by O(n). O(log n) is considered to be the fastest but as we have more of a larger inputs it starts to increase to O(n) or possibly O(n²). There are five Big O Notations that you’ll encounter a lot from fastest to slowest.
- O(log n), also known as log time. Example: Binary Search.
- O(n), also known as linear time. Example: Simple Search.
- O(n * log n). Example: A fast sorting algorithm, like Quicksort.
- O(n2). Example: A slow sorting algorithm, like Selection Sort.
- O(n!). Example: A really slow algorithm.
This chart gives you information on runtime from average to worst. You can see how some are better than other for certain situations and this chart can prove useful for future situations.
The main points of the Big O Notation that you should take away from this post.
- Big O Notation is measured by the growth of operations
- Run time is expressed in Big O Notation such as O(n), O(log n), etc.
- Understanding Big O Notation helps you grasp the important concept of efficiency in your programs
To be comfortable in knowing this information will give you an advantage in coding interviews and help you grasp the fundamental knowledge of coding efficiency, thanks to Big O Notation.
