This article gives a very high level of explanation, if you are looking for more detailed, please explore Wikipedia. What is Big O Notation? Big Oh or Big O notation is used to discover the performance or complexity of an algorithm.
Big O returns the upper bound (worst case scenario) for time complexity or space of an algorithm. In general, it is used in conjunction with processing data sets (lists) but can be used elsewhere.
Why it is required?
For a given problem, you always have more than one solutions (algorithms). To determine the most efficient algorithm out of available algorithms, Big O notation is being used. It helps to find the best algorithm in terms of efficiency or space based on requirement. So, Big O notation measures the efficiency of an algorithm based on the time/space, it takes for the algorithm to run as a function of the input size. Here, input can be a any data set - Array, ArrayList, Map, Linkedlist, Hashtable etc.
What are the limitations of the Big O Notation?
In next article, you will learn concepts that always kept you away from learning the Big O notation. Pointers to help you understand the complexity of Big-O
Big O returns the upper bound (worst case scenario) for time complexity or space of an algorithm. In general, it is used in conjunction with processing data sets (lists) but can be used elsewhere.
For a given problem, you always have more than one solutions (algorithms). To determine the most efficient algorithm out of available algorithms, Big O notation is being used. It helps to find the best algorithm in terms of efficiency or space based on requirement. So, Big O notation measures the efficiency of an algorithm based on the time/space, it takes for the algorithm to run as a function of the input size. Here, input can be a any data set - Array, ArrayList, Map, Linkedlist, Hashtable etc.
What are the limitations of the Big O Notation?
- Big O ignores constants whether it is constant overhead or constant factor. But sometimes in practical solutions, these can be substantial and can't be ignored.
- It is only useful for large data-sets. For small data-set, it is not useful.
- Few complex alogrithm are very hard to analyze mathematically.
- It can be only used for worst-case scenarios. For average case or best case, other alternative approaches are requried.
- There are some rules which is used to calcuate the Big O notation of an algorithm.
- Constant factors and overhead are completely ignored.
- When there are several term you identified while calculating the algorithm, only the largest term should be used. The order of the term is as follow: O(l) < O(log n) < O(n) < O(n log n) < O(n2) < O(n3) < O(an)
- Conditional statements are O(1).
- Linear loop equations are always O(n).
- In Nested loops, loops are multiplied.
- Sequential loops are added
In next article, you will learn concepts that always kept you away from learning the Big O notation. Pointers to help you understand the complexity of Big-O
Emoticon Emoticon