+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 writing 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 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