Engineer bro!

Sat Apr 30 2022 (3 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 $1{0}^{100}10^\left\{100\right\}$. 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:N\to {R}^{+}f,g: N \to R^+$ the max rule says that $O\left(f\left(n\right)+g\left(n\right)\right)=O\left(max\left(f\left(n\right),g\left(n\right)\right)\right)O\left(f\left(n\right) + g\left(n\right)\right) = O\left(max\left(f\left(n\right),g\left(n\right)\right)\right)$.

For example:

1. ${n}^{4}+100{n}^{2}+10n+50n^4+100n^2+10n+50$ is $O\left({n}^{4}\right)O\left(n^4\right)$

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

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

## Expressing functions in terms of Asymptotic Notations

Find big Oh notation for $f\left(n\right)={2}^{n}+6{n}^{2}+3nf\left(n\right) = 2^n + 6n^2 + 3n$

## Exercises

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

2. Express $20{n}^{3}+10n\mathrm{log}n+520n^3 + 10n \log n + 5$ in terms of $OO$ notation.

3. Express $5n\mathrm{log}n+2n5n \log n + 2n$ in terms of $OO$ notation.

4. Prove or Disprove

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

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

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

6. Find $\theta \theta$ notation for $3×{2}^{n}+4{n}^{2}+5n+23 \times 2^n + 4n^2 + 5n + 2$

7. Find $OO$ notation for the following function

1. ${2}^{n}+6{n}^{2}+3n2^n + 6n^2 + 3n$

2. $4{n}^{3}+2n+34n^3 + 2n + 3$

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

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

2. $5{n}^{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.