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 $$10^{100}10^\{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:

Here you can consider n as the price of elephant and $$100\times 10000100\; \backslash 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:N\to R^{+}f,g:\; N\; \backslash 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. $$n^4+100n^2+10n+50n^4+100n^2+10n+50$$ is $$O(n^4)O(n^4)$$

2. $$100n^3+2n^{2}100n^3\; +\; 2n^2$$ is $$O(n^3)O(n^3)$$

3. $$n^3-n^{2}n^3\; -\; n^2$$ is $$O(n^3)O(n^3)$$

Expressing functions in terms of Asymptotic Notations

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

Exercises

1. Express the function $$n^3\mathrm{/}100-100n^2-100n+3n^3/100\; -\; 100n^2\; -100n\; +\; 3$$ in terms of $$\theta \backslash theta$$ notation.

2. Express $$20n^3+10n\log n+520n^3\; +\; 10n\; \backslash log\; n\; +\; 5$$ in terms of $$OO$$ notation.

3. Express $$5n\log n+2n5n\; \backslash log\; n\; +\; 2n$$ in terms of $$OO$$ notation.

4. Prove or Disprove

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

   2. $$2^{2n}=O(2^n)2^\{2n\}\; =\; O(2^n)$$

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

6. Find $$\theta \backslash theta$$ notation for $$3\times 2^n+4n^2+5n+23\; \backslash times\; 2^n\; +\; 4n^2\; +\; 5n\; +\; 2$$

7. Find $$OO$$ notation for the following function

   1. $$2^n+6n^2+3n2^n\; +\; 6n^2\; +\; 3n$$

   2. $$4n^3+2n+34n^3\; +\; 2n\; +\; 3$$

8. Find $$\mathrm{\Omega }\backslash Omega$$ notation for the following functions

   1. $$4\ast 2n+3n4*2n\; +\; 3n$$

   2. $$5n^3+n^2+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 :)