Asymptotic Notations

  • June 19, 2017
+ADw-p+AD4-Here you will learn about Asymptotic Analysis and Asymptotic Notations in detail.+ADw-/p+AD4 +ADw-p+AD4-It is common that we write before code to any problem. There may exist more than one solution for a particular problem. But we need the solution which is better in +ADw-strong+AD4-time and space complexities+ADw-/strong+AD4. To compare and analyse algorithms complexities we do some analysis called +ADw-strong+AD4-Asymptotic Analysis. +ADw-/strong+AD4-That is, we are concerned with the how running time of an algorithm increases with the input. Usually an algorithm asymptotically more efficient will be the best choice.+ADw-/p+AD4 +ADw-p+AD4APA-strong+AD4-Also Read:+AKAAPA-a href+AD0AIg-http://www.thecrazyprogrammer.com/2017/05/analysis-of-algorithms.html+ACI rel+AD0AIg-noopener+ACIAPg-Analysis of Algorithms+ADw-/a+AD4APA-/strong+AD4APA-/p+AD4 +ADw-h2+AD4APA-strong+AD4-Asymptotic Notations+ADw-/strong+AD4APA-/h2+AD4 +ADw-p+AD4APA-strong+AD4-Asymptotic Notations+ADw-/strong+AD4 are mathematical tools to represent time complexity of algorithms for asymptotic analysis.+ADw-/p+AD4 +ADw-p+AD4-Most commonly used three asymptotic notations are:+ADw-/p+AD4 +ADw-h3+AD4-Big Oh Notation (O)+ADw-/h3+AD4 +ADw-p+AD4APA-img class+AD0AIg-aligncenter size-full wp-image-7746+ACI src+AD0AIg-http://www.thecrazyprogrammer.com/wp-content/uploads/2017/06/Big-Oh-Notation.png+ACI alt+AD0AIg-Big Oh Notation (O)+ACI width+AD0AIg-336+ACI height+AD0AIg-327+ACI srcset+AD0AIg-http://www.thecrazyprogrammer.com/wp-content/uploads/2017/06/Big-Oh-Notation.png 336w, http://www.thecrazyprogrammer.com/wp-content/uploads/2017/06/Big-Oh-Notation-300x292.png 300w+ACI sizes+AD0AIg(max-width: 336px) 100vw, 336px+ACI /+AD4APA-/p+AD4 +ADw-p+AD4-It is represented by +ADw-strong+AD4-O+ADw-/strong+AD4 (capital alphabet O). See the above diagram.+ADw-/p+AD4 +ADw-p+AD4-The function f(n) represents that, how running time of the program is increasing when giving larger inputs to the problem.+ADw-/p+AD4 +ADw-p+AD4-Now, we try to find what is the worst case or upper bound of the function f(n). So we draw another function g(n) which is always greater than f(n) after some limit n +AD0 n+ADw-sub+AD4-0+ADw-/sub+AD4.+ADw-/p+AD4 +ADw-p+AD4-Therefore we say f(n) +AD0 O(g(n)), in the condition that, f(n) +ACY-lt+ADsAPQ c g(n), where n +ACY-gt+ADsAPQ n+ADw-sub+AD4-0.+ADw-/sub+AD4, c +ACY-gt+ADs 0, n+ADw-sub+AD4-0+AKAAPA-/sub+AD4AJg-gt+ADsAPQ 1.+ADw-/p+AD4 +ADw-p+AD4-This says that f(n) is smaller than g(n).+ADw-strong+AD4AoAA8-/strong+AD4APA-/p+AD4 +ADw-p+AD4APA-strong+AD4-Example+ADw-/strong+AD4APA-/p+AD4 +ADw-p+AD4-Let f(n) +AD0 3n+ACs-2+ADs g(n) +AD0 n. To say that f(n) +AD0 O g(n),+ADw-/p+AD4 +ADw-p+AD4-We need to prove that, f(n) +ACY-lt+ADsAPQ cg(n)+ADs where c +ACY-gt+ADs 0, n+ADw-sub+AD4-0+AKAAPA-/sub+AD4AJg-gt+ADsAPQ 1+ADw-/p+AD4 +ADw-p+AD4-3n+ACs-2 +ACY-lt+ADsAPQ cn+ADs If we substitute c +AD0 4, then 3n+ACs-2 +ACY-lt+ADsAPQ 4n. If we simplify n +ACY-gt+ADsAPQ 2.+ADw-/p+AD4 +ADw-p+AD4-Therefore for every n +ACY-gt+ADsAPQ 2 and c +AD0 4, f(n) +ACY-lt+ADsAPQ c g(n). So f(n) +AD0 O g(n).+ADw-/p+AD4 +ADw-p+AD4-Here we proved that, n is bounding given function so definitely greater than +IBw-n+IB0, those are n+ADw-sup+AD4-2+ADw-/sup+AD4, n+ADw-sup+AD4-3+ADw-/sup+AD4.. also upper bound this function. But as per Big-O definition, we are interested in +ADw-strong+AD4-tightest (closest) upper bound.+ADw-/strong+AD4 That is the reason we write 3n+ACs-2 +AD0 O(n).+ADw-/p+AD4 +ADw-h3+AD4-Big Omega Notation (+A6k)+ADw-/h3+AD4 +ADw-p+AD4APA-img class+AD0AIg-aligncenter size-full wp-image-7747+ACI src+AD0AIg-http://www.thecrazyprogrammer.com/wp-content/uploads/2017/06/Big-Omega-Notation.png+ACI alt+AD0AIg-Big Omega Notation (+A6k)+ACI width+AD0AIg-313+ACI height+AD0AIg-312+ACI srcset+AD0AIg-http://www.thecrazyprogrammer.com/wp-content/uploads/2017/06/Big-Omega-Notation.png 313w, http://www.thecrazyprogrammer.com/wp-content/uploads/2017/06/Big-Omega-Notation-150x150.png 150w, http://www.thecrazyprogrammer.com/wp-content/uploads/2017/06/Big-Omega-Notation-300x300.png 300w+ACI sizes+AD0AIg(max-width: 313px) 100vw, 313px+ACI /+AD4APA-/p+AD4 +ADw-p+AD4-It is represented by Greek letter +ADw-strong+AD4DqQA8-/strong+AD4.+ADw-/p+AD4 +ADw-p+AD4-See the above picture, the actual increasing function of the algorithm is f(n). And we want to give a lower bound for that, it is cg(n).+ADw-/p+AD4 +ADw-p+AD4-cg(n) is less than f(n) after some value of n +AD0 n+ADw-sub+AD4-0+ADw-/sub+AD4.+ADw-/p+AD4 +ADw-p+AD4-f(n) +ACY-gt+ADsAPQ cg(n) , n +ACY-gt+ADsAPQ n+ADw-sub+AD4-0+ADw-/sub+AD4, c +ACY-gt+ADs 0, n+ADw-sub+AD4-0+AKAAPA-/sub+AD4AJg-gt+ADsAPQ 1.+ADw-/p+AD4 +ADw-p+AD4-If it satisfies above conditions we say, g(n) is smaller than f(n).+ADw-/p+AD4 +ADw-p+AD4APA-strong+AD4-Example+ADw-/strong+AD4APA-/p+AD4 +ADw-p+AD4-Let, f(n) +AD0 3n+ACs-2. g(n) +AD0 n.+ADw-/p+AD4 +ADw-p+AD4-Now check can this f(n) has lower bound as g(n) or not.+ADw-/p+AD4 +ADw-p+AD4-f(n) +AD0 +A6k g(n), this will happen only if f(n) +ACY-gt+ADsAPQ c g(n).+ADw-/p+AD4 +ADw-p+AD4-i.e 3n+ACs-2 +ACY-gt+ADsAPQ cn.+AKA Here c +AD0 1 and n+ADw-sub+AD4-0 +ADw-/sub+AD4AJg-gt+ADsAPQ 1. This is satisfied so f(n) +AD0 +A6k g(n).+ADw-/p+AD4 +ADw-p+AD4-Therefore, 3n+ACs-2 is lower bounded by +ADw-strong+AD4-n. +ADw-/strong+AD4-Here also since +ADw-strong+AD4-n+ADw-/strong+AD4 is lower bound of 3n+ACs-2, anything less than n also lower bound to 3n+ACs-2. That log(n), log log(n), like that. But as per definition we should take +ADw-strong+AD4-tightest lower bound+ADw-/strong+AD4, which is n.+ADw-/p+AD4 +ADw-h3+AD4-Big Theta Notation (+A5gAPA-strong+AD4)+ADw-/strong+AD4APA-/h3+AD4 +ADw-p+AD4APA-img class+AD0AIg-aligncenter size-full wp-image-7748+ACI src+AD0AIg-http://www.thecrazyprogrammer.com/wp-content/uploads/2017/06/Big-Theta-Notation.png+ACI alt+AD0AIg-Big Theta Notation (+A5g)+ACI width+AD0AIg-311+ACI height+AD0AIg-318+ACI srcset+AD0AIg-http://www.thecrazyprogrammer.com/wp-content/uploads/2017/06/Big-Theta-Notation.png 311w, http://www.thecrazyprogrammer.com/wp-content/uploads/2017/06/Big-Theta-Notation-293x300.png 293w+ACI sizes+AD0AIg(max-width: 311px) 100vw, 311px+ACI /+AD4APA-/p+AD4 +ADw-p+AD4-This represented by Greek letter +ADw-strong+AD4DmAA8-/strong+AD4.+ADw-/p+AD4 +ADw-p+AD4-See the above picture, f(n) is actual growing function. We should find the both the upper bound and lower bound just by varying the constant c, with same function+ADw-strong+AD4. +ADw-/strong+AD4-Here that function is g(n).+ADw-/p+AD4 +ADw-p+AD4-If f(n) is bounded by c1 g(n) and c2 g(n) we can say that f(n) +AD0 +A5gAoA-g(n). Constants c1 and c2 could be different.+ADw-/p+AD4 +ADw-p+AD4-Therefore we say f(n) +AD0 +A5gAoA-g(n) , if f(n) is bounded by g(n) +ADw-strong+AD4-both in the lower and upper.+ADw-/strong+AD4APA-/p+AD4 +ADw-p+AD4-c1 g(n) +ACY-lt+ADsAPQ f(n) +ACY-lt+ADsAPQ c2 g(n), where c1, c2 +ACY-gt+ADs 0, n +ACY-gt+ADsAPQ n+ADw-sub+AD4-0+ADw-/sub+AD4, n+ADw-sub+AD4-0+ADw-/sub+AD4 +ACY-gt+ADsAPQ 1.+ADw-/p+AD4 +ADw-p+AD4APA-strong+AD4-Example+ADw-/strong+AD4APA-/p+AD4 +ADw-p+AD4-F(n) +AD0 3n+ACs-2, g(n) +AD0 n.+ADw-/p+AD4 +ADw-p+AD4-F(n) +ACY-lt+ADsAPQ c g(n) where c +AD0 4+ADs That is 3n+ACs-2 +ACY-lt+ADsAPQ 4n. This is valid for all n+ADw-sub+AD4-0+AKAAPA-/sub+AD4AJg-gt+ADsAPQ 1.+ADw-/p+AD4 +ADw-p+AD4-So we can say g(n) is upper bound for f(n). Now see it is as well as lower bound also.+ADw-/p+AD4 +ADw-p+AD4-F(n) +ACY-gt+ADsAPQ c g(n)+ADs That is 3n+ACs-2 +ACY-gt+ADsAPQCg n. where n+ADw-sub+AD4-0+ADw-/sub+AD4 +ACY-gt+ADsAPQ 1.+ADw-/p+AD4 +ADw-p+AD4-So both the cases are valid for this.+ADw-/p+AD4 +ADw-p+AD4-This theta notation also called asymptotically equal.+ADw-/p+AD4 +ADw-p+AD4APA-strong+AD4-Applications of These Notations in Algorithms+ADw-/strong+AD4APA-/p+AD4 +ADw-ul+AD4 +ADw-li+AD4-The Big-O notation says the +ADw-strong+AD4-worst case+ADw-/strong+AD4AoA-complexity of the algorithm. That means with any large amount of input, that program never exceeds this complexity.+ADw-/li+AD4 +ADw-li+AD4-The Big-Omega notation says that+AKAAPA-strong+AD4-best case+ADw-/strong+AD4AoA-complexity of the algorithm. That means with any small input, the program never executes less than this complexity.+ADw-/li+AD4 +ADw-li+AD4-Theta notation gives the +ADw-strong+AD4-average case +ADw-/strong+AD4-of complexity.+ADw-/li+AD4 +ADw-li+AD4-Most of the cases we are interested in what is the worst case complexity of the program.+ADw-/li+AD4 +ADw-/ul+AD4 +ADw-p+AD4-For more understanding, see the example below.+ADw-/p+AD4 +ADw-p+AD4-Let there is an array of +IBw-n+IB0 elements. We want to search an element +IBw-x+IB0 in that array.+ADw-/p+AD4 +ADw-p+AD4-If we do linear search we may find that element at first index i.e in +A6k (1) time. This is the best case of this algorithm.+ADw-/p+AD4 +ADw-p+AD4-In worst case our element +IBw-x+IB0 many not exists in array. In that case we must check all elements and end up with no result. i.e O (n) time. This is the worst case of this algorithm.+ADw-/p+AD4 +ADw-p+AD4-Average case is, at some index of array we find that element i.e +A5g (n/2) complexity.+ADw-/p+AD4 +ADw-p+AD4APA-strong+AD4-Some common asymptotic notations are:+ADw-/strong+AD4APA-/p+AD4 +ADw-p+AD4-Constant time: O(1)+ADw-/p+AD4 +ADw-p+AD4-Logarithmic: O(log n)+ADw-/p+AD4 +ADw-p+AD4-Linear: O(n)+ADw-/p+AD4 +ADw-p+AD4-Quadratic: O(n+ADw-sup+AD4-2+ADw-/sup+AD4)+ADw-/p+AD4 +ADw-p+AD4-Cubic: O(n+ADw-sup+AD4-3+ADw-/sup+AD4)+ADw-/p+AD4 +ADw-p+AD4-Polynomial: n+ADw-sup+AD4-O(1)+ADw-/sup+AD4APA-/p+AD4 +ADw-p+AD4-Exponential: 2+ADw-sup+AD4-O(n)+ADw-/sup+AD4APA-/p+AD4 +ADw-p+AD4-Comment below if you have queries or found any information incorrect in above for asymptotic notations.+ADw-/p+AD4 +ADw-p+AD4-The post +ADw-a rel+AD0AIg-nofollow+ACI href+AD0AIg-http://www.thecrazyprogrammer.com/2017/06/asymptotic-notations.html+ACIAPg-Asymptotic Notations+ADw-/a+AD4 appeared first on +ADw-a rel+AD0AIg-nofollow+ACI href+AD0AIg-http://www.thecrazyprogrammer.com+ACIAPg-The Crazy Programmer+ADw-/a+AD4.+ADw-/p+AD4

Neeraj Mishra, founder of The Crazy Programmer. He is programming lover and professional blogger from India. He spends most of his time in doing programming and helping other programmers.


Subscribe to our newsletter!

More from our blog

See all posts
No Comments
 

Leave a Comment