0
3.5kviews
Explain Asymptotic notations. Explain time complexity and space complexity in details.
1 Answer
1
331views

Asymptotic Notation : -

Asymptotic Notation is used to describe the running time of an algorithm - how much time an algorithm takes with a given input, n.


There are three different notations:

  1. Big O Notation
  2. Big Theta (Θ) Notation
  3. Big Omega (Ω) Notation


Big-Θ is used when the running time is the same for all cases, Big-O for the worst case running time, and Big-Ω for the best case running time.



Big Θ notation : -

We compute the big-Θ of an algorithm by counting the number of iterations the algorithm always takes with an input of n. For instance, the loop in the pseudo code below will always iterate N times for a list size of N. The runtime can be described as Θ(N).



Big-O Notation : -

The Big-O notation describes the worst-case running time of a program. We compute the Big-O of an algorithm by counting how many iterations an algorithm will take in the worst-case scenario with an input of N. We typically consult the Big-O because we must always plan for the worst case. For example, O(log n) describes the Big-O of a binary search algorithm.



Big-Ω Notation : -

Big-Ω (Omega) describes the best running time of a program. We compute the big-Ω by counting how many iterations an algorithm will take in the best-case scenario based on an input of N. For example, a Bubble Sort algorithm has a running time of Ω(N) because in the best case scenario the list is already sorted, and the bubble sort will terminate after the first iteration.




Time Complexity and Space Complexity : -

Time Complexity -

The time complexity of an algorithm is the amount of time taken by the algorithm to complete its process as a function of its input length, n. The time complexity of an algorithm is commonly expressed using asymptotic notations:

  • Big O - O(n),
  • Big Theta - Θ(n)
  • Big Omega - Ω(n)



Space Complexity -

The space complexity of an algorithm is the amount of space (or memory) taken by the algorithm to run as a function of its input length, n. Space complexity includes both auxiliary space and space used by the input.

Please log in to add an answer.