The efficiency and accuracy of algorithms have to be analysed to compare them and choose a specific algorithm for certain scenarios.
The process of making this analysis is called Asymptotic analysis. It
refers to computing the running time of any operation in mathematical units of computation. For example, the running time of one operation is computed as f(n) and may be for another operation it is computed as g(n2). This means the first operation running time will increase linearly with the increase in n and the running time of the second operation will increase exponentially when n increases. Similarly, the running time of both operations will be nearly the same if n is significantly small.

Usually, the time required by an algorithm falls under three types −

Best Case ? Minimum time required for program execution.

Average Case ? Average time required for program execution.

Worst Case ? Maximum time required for program execution.

Asymptotic Notations

Following are the commonly used asymptotic notations to calculate the running time complexity of an algorithm.

Ο Notation

Ω Notation

θ Notation

Big Oh Notation, Ο

The notation Ο(n) is the formal way to express the upper bound of an algorithm's running time. It measures the worst case time complexity or the longest amount of time an algorithm can possibly take to complete.

Ο(f(n)) = { g(n) : there exists c > 0 and n_{0} such that f(n) ≤ c.g(n) for all n > n_{0}. }

Omega Notation, Ω

The notation Ω(n) is the formal way to express the lower bound of an algorithm's running time. It measures the best case time complexity or the best amount of time an algorithm can possibly take to complete.

For example, for a function f(n)

Ω(f(n)) ≥ { g(n) : there exists c > 0 and n_{0} such that g(n) ≤ c.f(n) for all n > n_{0}. }

Theta Notation, θ

The notation θ(n) is the formal way to express both the lower bound and the upper bound of an algorithm's running time. It is represented as follows −

θ(f(n)) = { g(n) if and only if g(n) = Ο(f(n)) and g(n) = Ω(f(n)) for all n > n_{0}. }

Common Asymptotic Notations

Following is a list of some common asymptotic notations −

constant

−

Ο(1)

logarithmic

−

Ο(log n)

linear

−

Ο(n)

n log n

−

Ο(n log n)

quadratic

−

Ο(n^{2})

cubic

−

Ο(n^{3})

polynomial

−

n^{Ο(1)}

exponential

−

2^{Ο(n)}

Frequently Asked Questions

+

Ans: Python Data Structure Introduction - Learn Python Data Structure in simple and easy steps starting from basic to advanced concepts with examples including Introduction, Environment, Arrays, Lists, Tuples, Dictionary, 2-D Array, Matrix, Sets, Maps, Linked Lists, Stack, Queue, Dequeue, Advanced Linked list, Hash Table, Binary Tree, Search Tree, Heaps, Graphs, Algorithm Design, Divide and conquer, Recursion, backtracking, Tree Traversal, Sorting, Searching, Graph Algorithms, Algorithm Analysis, Big-O Notation, Algorithim classes, Amortized analysis, Algorithm Justifications. view more..

+

Ans: Python Data Structure Introduction - Learn Python Data Structure in simple and easy steps starting from basic to advanced concepts with examples including Introduction, Environment, Arrays, Lists, Tuples, Dictionary, 2-D Array, Matrix, Sets, Maps, Linked Lists, Stack, Queue, Dequeue, Advanced Linked list, Hash Table, Binary Tree, Search Tree, Heaps, Graphs, Algorithm Design, Divide and conquer, Recursion, backtracking, Tree Traversal, Sorting, Searching, Graph Algorithms, Algorithm Analysis, Big-O Notation, Algorithim classes, Amortized analysis, Algorithm Justifications. view more..

+

Ans: Python Data Structure Introduction - Learn Python Data Structure in simple and easy steps starting from basic to advanced concepts with examples including Introduction, Environment, Arrays, Lists, Tuples, Dictionary, 2-D Array, Matrix, Sets, Maps, Linked Lists, Stack, Queue, Dequeue, Advanced Linked list, Hash Table, Binary Tree, Search Tree, Heaps, Graphs, Algorithm Design, Divide and conquer, Recursion, backtracking, Tree Traversal, Sorting, Searching, Graph Algorithms, Algorithm Analysis, Big-O Notation, Algorithim classes, Amortized analysis, Algorithm Justifications. view more..

+

Ans: Python Data Structure Introduction - Learn Python Data Structure in simple and easy steps starting from basic to advanced concepts with examples including Introduction, Environment, Arrays, Lists, Tuples, Dictionary, 2-D Array, Matrix, Sets, Maps, Linked Lists, Stack, Queue, Dequeue, Advanced Linked list, Hash Table, Binary Tree, Search Tree, Heaps, Graphs, Algorithm Design, Divide and conquer, Recursion, backtracking, Tree Traversal, Sorting, Searching, Graph Algorithms, Algorithm Analysis, Big-O Notation, Algorithim classes, Amortized analysis, Algorithm Justifications. view more..

+

Ans: Python Data Structure Algorithm Classes - Learn Python Data Structure in simple and easy steps starting from basic to advanced concepts with examples including Introduction, Environment, Arrays, Lists, Tuples, Dictionary, 2-D Array, Matrix, Sets, Maps, Linked Lists, Stack, Queue, Dequeue, Advanced Linked list, Hash Table, Binary Tree, Search Tree, Heaps, Graphs, Algorithm Design, Divide and conquer, Recursion, backtracking, Tree Traversal, Sorting, Searching, Graph Algorithms, Algorithm Analysis, Big-O Notation, Algorithim classes, Amortized analysis, Algorithm Justifications. view more..

+

Ans: Python Data Structure Introduction - Learn Python Data Structure in simple and easy steps starting from basic to advanced concepts with examples including Introduction, Environment, Arrays, Lists, Tuples, Dictionary, 2-D Array, Matrix, Sets, Maps, Linked Lists, Stack, Queue, Dequeue, Advanced Linked list, Hash Table, Binary Tree, Search Tree, Heaps, Graphs, Algorithm Design, Divide and conquer, Recursion, backtracking, Tree Traversal, Sorting, Searching, Graph Algorithms, Algorithm Analysis, Big-O Notation, Algorithim classes, Amortized analysis, Algorithm Justifications. view more..

+

Ans: Python Data Structure Introduction - Learn Python Data Structure in simple and easy steps starting from basic to advanced concepts with examples including Introduction, Environment, Arrays, Lists, Tuples, Dictionary, 2-D Array, Matrix, Sets, Maps, Linked Lists, Stack, Queue, Dequeue, Advanced Linked list, Hash Table, Binary Tree, Search Tree, Heaps, Graphs, Algorithm Design, Divide and conquer, Recursion, backtracking, Tree Traversal, Sorting, Searching, Graph Algorithms, Algorithm Analysis, Big-O Notation, Algorithim classes, Amortized analysis, Algorithm Justifications. view more..

+

Ans: Python Network Programming - Learn Python Network Programming in simple and easy steps starting from basic to advanced concepts with examples. view more..

+

Ans: Python Network Programming Introduction - Learn Python Network Programming in simple and easy steps starting from basic to advanced concepts with examples. view more..

+

Ans: Python Netwrok Environment - Learn Python Network Programming in simple and easy steps starting from basic to advanced concepts with examples. view more..

+

Ans: Python Internet Protocol - Learn Python Network Programming in simple and easy steps starting from basic to advanced concepts with examples. view more..

+

Ans: Python IP Address - Learn Python Network Programming in simple and easy steps starting from basic to advanced concepts with examples. view more..

+

Ans: Python DNS Look-up- Learn Python Network Programming in simple and easy steps starting from basic to advanced concepts with examples. view more..

+

Ans: Python Routing - Learn Python Network Programming in simple and easy steps starting from basic to advanced concepts with examples. view more..

+

Ans: Python HTTP Requests - Learn Python Network Programming in simple and easy steps starting from basic to advanced concepts with examples. view more..

+

Ans: Python HTTP Response - Learn Python Network Programming in simple and easy steps starting from basic to advanced concepts with examples. view more..

+

Ans: Python Headers - Learn Python Network Programming in simple and easy steps starting from basic to advanced concepts with examples. view more..

+

Ans: Python Custom HTTP Requests - Learn Python Network Programming in simple and easy steps starting from basic to advanced concepts with examples. view more..