Engineer bro!
Sat Apr 30 2022 (3 months ago)
Engineer by mistake!
I am a software engineer by passion
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.
100K
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 . 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 as price of coffee. So, overall time complexity can be specified as the order of n by ignoring constants.
Maximum rule says that low order terms in a function are relatively insignificant for large n.
Let, the max rule says that .
For example:
is
is
is
Find big Oh notation for
Express the function in terms of notation.
Express in terms of notation.
Express in terms of notation.
Prove or Disprove
Check the correctness of the following equality,
Find notation for
Find notation for the following function
Find notation for the following functions
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 :)
© 2021 dsabyte. All rights reserved
Comments (0)