When you write an algorithm or solve some computational problem you would often like to have an efficient working code. In normal language we would say its fast or slow or fast enough. Well the term is quote OK to use but to be quantitative we have notations which could be used here. These notation are called Asymptotic Notations. So to keep it simple these are notations to analyze an algorithm on how it performs when given a certain input.
Types of notations
- Big-O (Big O) [Atmost or Upper Bound]
- Big-Ω (Big-Omega) [AtLeast or Lower Bound]
- Big-θ (Big Theta) [Range or Tight Bound]
1.Big-O (Big O)
This notation is used to define the upper bound of an algorithm or define the worst case of an algorithm.
Mathematical notation: f(n) = O(g(n)). Where positive constants c and n0 such that 0 ≤ f(n) ≤ c*g(n) for all n ≥ n0
Graphical Representation:
Now, Big-O notation is the most popular one, and mostly when we talk about time complexity its usually related to Big-O.
Big-O has several notations. Lets see one by one.
- Constant - O(1)
It means that no mater what the input size be, the execution time will always be the same.
Example:
item = items[0]
Graphical Representation:
- Linear - O(n)
It means that the execution time is in direct propotion to the input i.e. if the input size increases or decreases so does the execution time increases or decreases.
Example:
element_found = [x for i,x in enumerate([2,3,5]) if x==5]
In the above example searching an element in a linear search manner.
Graphical Representation
- Quadratic - O(n2)
It means that the execution time of an algorithm is directly proportion to the square of the size of the input.
Example:
for i in [2,3,4,5]:
for z in [5,4,3,2]:
print(f"Match {z}") if i == z else ''
Above example has nested loop which makes it a quadratic operation.
Graphical Representation
- Exponential - O(2n)
It means the execution time will double with each additional element in the input set.
Example:
def fibonacci(n):
if n <= 1:
return n
else:
return((fibonacci(n-1) + fibonacci(n-2)))
Graphical Representation
- Logarithmic - O(log(n))
If an algorithm solves the problem by dividing it into half each time then its a O(log n). A great example of it is Binary Search Algorithm.
Graphical Representation
As you can see with the graph that with initial input it tends to grow but with increase in input size it gradually stops growing or grows at a linear rate. Its very much suitable for larger input set.
- Factorial - O(!n)
Is an algorithm which tries all the permutation of a given input array. Its one of the worst performaning algorithm hence you dont want your algorithm to be to this level.
Example:
Most commonly talked about factorial complexity algorithm is Travelling Salesman problem when does using Brute force method, where all the possible path combinations are evaluated. Another example is to get the factorial of a number.
def factorial(n):
for i in range(n):
factorial(n-1)
Outer loop is O(n), inner function is called recursively with (n-1) you get n * (n-1)* (n-2)*...*1 = n! so the function is O(n!).
2.Big-Ω (Big-Omega)
This notation is used to define the lower bound of an algorithm. So we can say a given algorithm will take atleast a certain amount of time.
Mathematical notation: f(n) = Ω(g(n)). Where positive constants c and n0 such that 0 ≤ c*g(n) ≤ f(n) for all n ≥ n0
Graphical Representation:
Example:
In case of Binary search algorithm we can say that it has its best case as Ω(1), if the number you are finding falls right in the middle.
3.Big-Θ (Big-Theta)
This notation defines a tight bound of an algorithim execution time. So, there is an upper bound and a lower bound and the algorithm execution time would fall within the range.
Mathematical notation: f(n) = θ(g(n)). Where positive constants n0, c1, c2 are such that at the right of n0 , the value of f(n) always lies between c1g(n) and c2g(n) i.e. 0 ≤ c1g(n) ≤ f(n) ≤ c2g(n) for all n ≥ n0
Graphical Representation:
Example:
def search_index(num):
for i, x in enumerate(list):
if num == x:
return i
In the above example, lower bound (best case) would be O(1) where the item is found at 0 index. And upper bound (worst case) would be O(n) where the item is found at the last index.
Readings and References:
http://web.mit.edu/16.070/www/lecture/big_o.pdf
https://i.stack.imgur.com/nLm8w.png
https://guide.freecodecamp.org/computer-science/notation/big-o-notation/
https://stackabuse.com/big-o-notation-and-algorithm-analysis-with-python-examples/
https://www.daveperrett.com/articles/2010/12/07/comp-sci-101-big-o-notation/
Top comments (0)