Big O notation is one of the very important parts of solving an algorithm in coding interviews.
At a point, I was lost on my journey of trying to really understand what big O notation was all about in different algorithms problems because its base on the measurement of better implementation which means faster time (processing time) to run and to use less memory (RAM usage) on a different piece of code, sometimes I tried guessing but was always wrong because there is a concept to measuring the space and time complexity of an algorithm, which I'm going to share with you on this article to help you ace your next coding interviews.
Here’s what will be covered:
- What is Big O notation
- Why does Big O Notation matter?
- What does better performance mean
- What are time and space complexity
- Common forms of Big O Notation
What is Big O Notation:
Big O notation is a mathematical notation that gives us a precise and efficient representation for judging an algorithm task performance. The big O notation is generally the most used among other notations because it focuses on the worst-case scenario: meaning where most operations are needed to complete the task.
Big 0 notation is the language we use for talking about how long an algorithm takes to run. It's literally how we compare the efficiency of different approaches to a problem.
Why does Big O Notation matter?
Writing good software or an algorithm is largely about understanding and making informed decisions about trade-offs in your design. Like considering the faster time(processing time) and memory usage to determine its efficiency and performance.
Big O notation practically tells you how algorithms scale with large numbers of inputs, an example is if your boss tells you to find the address of a special client by their name and you are given a huge pile of unsorted papers and an address book indexed by name!
In big-O notation, this is O(n) - running through your huge pile of unsorted paper, and O(1) - looking up the index by name.
Think of efficiency and performance!
What does better performance mean?
With big O notation, we express performance and the runtime in terms of how quickly it grows relative to the input, as the inputs get arbitrarily large. Considering the faster time(processing time) and less memory usage(RAM usage).
What are time and space complexity
When talking about Big O Notation it's essential to understand the concepts of time and space complexity.
There are two kinds of complexities in measuring the efficiency of an algorithm. Time complexity and space complexity which are approximations of how much time and how much space an algorithm will take to process certain inputs.
There are three cases to solve for in an algorithm which is known as asymptotic notations, and they are:
Best case - represented as Big Omega
Average case - represented as Big Theta
Worst case - represented as Big O Notation
Typically developers solve for the worst-case scenario, Big O because you're not expecting your algorithm to run in the best or even average cases. It allows you to make analytical decisions when solving a problem.
Common forms of Big O Notations
O(1) - Constant time complexity
This means a constant runtime, regardless of the size of the input, the algorithm will have the same runtime.
Example: Array - inserting or retrieving an element
O(log n) - Logarithmic time complexity
O(log n) means that time goes up linearly, while the n goes up exponentially.
Example: Binary tree - inserting or retrieving an element
O(n) - Linear time complexity
O(n) describes an algorithm whose performance will grow linearly and in direct proportion to the size of the input data set.
Example: Depth-first search (DFS) of a tree
O(n²) - Quadratic time complexity
As the elements in your list increase the time it will take for your algorithm to run will increase exponentially.
Example: Sorting algorithm: Bubble sort and insertion sort
Overall Big O Notation gives us a precise and objective way of judging an algorithm performance with its space and time complexity. How you should make a habit of thinking about the time and space complexity of algorithms as you design them.
Happy Hacking!😎