Engineer bro!

Sat Apr 30 2022 (5 months ago)

Engineer by mistake!

I am a software engineer by passion

Asymptotic analysis in practice

So far we have seen that what Asymptotic analysis is. In this article we'll explore the uses of Asymptotic analysis.

Consider a case where you have bought an elephant and a coffee. Where as cost of elephant is about ~100K and cost of coffee is about ~0.02k. A person is asking to you about the total money spended while buying elephant and coffee, then what will be your answer.

  1. 100K

  2. 100.02k

Off-course your answer will 100K instead of 100.02k, because 0.02k is negligible. The same concept is also applicable in Asymptotic analysis.

Let's consider below program:

for(var i=0; i<n; i++){ // loop1
    for(var j=0; j<100; j++){ // loop2
        // do nothing 
    }
    
    for(var j=1; j<10000; j++){ // loop3
        // do nothing
    }
}

In the above program n could be as large as user wants, it could be 1, 2, 100, or 1010010^{100}. But, loop2 and loop3 will run for a constant amount of time.

loop2 and loop3 is not dependent on the value of n. loop2 will run 100 times for every iteration of loop1 and loop3 will run 10000 times for every iteration of loop1.

So, overall time complexity can be specified as:

n×100×10000n \times 100 \times 10000

Here you can consider n as the price of elephant and 100×10000100 \times 10000 as price of coffee. So, overall time complexity can be specified as the order of n by ignoring constants.

Maximum rule

Maximum rule says that low order terms in a function are relatively insignificant for large n.

Let, f,g:NR+f,g: N \to R^+ the max rule says that O(f(n)+g(n))=O(max(f(n),g(n)))O(f(n) + g(n)) = O(max(f(n),g(n))).

For example:

  1. n4+100n2+10n+50n^4+100n^2+10n+50 is O(n4)O(n^4)

  2. 100n3+2n2100n^3 + 2n^2 is O(n3)O(n^3)

  3. n3n2n^3 - n^2 is O(n3)O(n^3)

Expressing functions in terms of Asymptotic Notations

Find big Oh notation for f(n)=2n+6n2+3nf(n) = 2^n + 6n^2 + 3n

    2n+6n2+3n2n+6n2+n2    2n+7n22n+2n    f(n)4n    C=2,g(n)=2nSo, f(n)=O(2n)\implies 2^n + 6n^2 + 3n \leq 2^n + 6n^2 + n^2 \\ \implies 2^n + 7n^2 \leq 2^n + 2^n \\ \implies f(n) \leq 4^n \\ \implies C = 2, g(n) = 2^n \\ So, \space f(n) = O(2^n)

Exercises

  1. Express the function n3/100100n2100n+3n^3/100 - 100n^2 -100n + 3 in terms of θ\theta notation.

  2. Express 20n3+10nlogn+520n^3 + 10n \log n + 5 in terms of OO notation.

  3. Express 5nlogn+2n5n \log n + 2n in terms of OO notation.

  4. Prove or Disprove

    1. 2n+1=O(2n)2^{n+1} = O(2^n)

    2. 22n=O(2n)2^{2n} = O(2^n)

  5. Check the correctness of the following equality, 5n3+2n=O(n3)5n^3 + 2n = O(n^3)

  6. Find θ\theta notation for 3×2n+4n2+5n+23 \times 2^n + 4n^2 + 5n + 2

  7. Find OO notation for the following function

    1. 2n+6n2+3n2^n + 6n^2 + 3n

    2. 4n3+2n+34n^3 + 2n + 3

  8. Find Ω\Omega notation for the following functions

    1. 42n+3n4*2n + 3n

    2. 5n3+n2+3n+25n^3 + n^2 + 3n + 2

Conclusion

We have seen Asymptotic analysis in practice, expressing functions in terms of Asymptotic notations. We have also given you some exercises for practice.

Thanks for reading this article :)

Design And Analysis of AlgorithmsData StructureSoftware Engineering

Comments (0)

Discussions (0)


© 2021 dsabyte. All rights reserved