What is BIG-O Notation, space, and time complexity?
A quick introduction to Big-O notation
Understanding Big -O Notation
BIG -O notation Is one of the most important topics in computer science also one of the confusing topics.
In this article, I am going to make it easy for you to understand Big -O notation with examples.
1. What is Big-O Notation?
Big-O notation is basically used to describe the complexity of an algorithm. That means it explains how much time and space an algorithm is going to take to complete the task.
For example, let’s take a task that needs to sort the elements of an array in a particular order. We have different algorithms for performing a single task.
Some of the algorithms may be quicker, some might take more space, and some of them might be better in all regards.
Some algorithms that you think are performing well might fail when the amount of data becomes big. So, when you are coding, it is important to understand what your code is doing and how it will perform with the data you have.
Here’s where the Big -O Notation comes to play. The basic idea is to analyze your algorithm in terms of speed and memory usage according to the size of the data.
2. How to measure Big-O notation
Big-O Notation tells whether the algorithm is slow or fast and how much slower it is and how much space it takes up compared to other similar algorithms based on the same given data.
We use some terminology to describe the Big-O notation such as :
Here we can consider “n” as the number of steps.
Consider an example of searching a particular number in an unsorted array to understand this. We are iterating over the array one by one to find the number.
If the number is at the end of the array, then you have to take “n” steps to find that number. Hence the complexity is taken as O(n).
In another case, When you search the same number you may find that as the very first element in the array. So, you have found it on your first try. Hence the complexity will be O(1) Which is a constant time.
Here, O(1) is the best-case scenario. But, Big-O notation focuses on the worst-case scenario (Since it’s a notation to find how our algorithm will perform in the scenario where the data might be too big). In our example, the worst-case complexity is O(n).
Hence, Big-O notation expresses the upper bound, which means the longest time an algorithm can take to complete.
Some of the common algorithms and their run times in BIG -O Notation are:
3. The Importance of BIG -O Notation
Being a computer science student or a software developer, it is important to understand Big-O Notation to analyze the different types of algorithms.
The Solid understanding of this will allow you to compare algorithms depending upon your type of data and to choose which is likely to behave better for you. (Also, the Big-O Notation is one of the favorite topics of interviewers)
If you are preparing for your interview, increasing your knowledge on the concept of Big-O Notation will help you to impress the interviewer and to land that position.
That’s all for this part 4 and this ends this series of Dart Basics. I hope you all liked this part! If you did so then smash that clap button. Also, don’t forget to leave constructive comments if you think there is room for improvement.
You can follow me on LinkedIn, Github, and Twitter.
You can click here to read the previous one.
Don’t forget to follow The Lean Programmer Publication for more such articles, and subscribe to our newsletter tinyletter.com/TheLeanProgrammer
