Free 5-Day Mini-Course: backtobackswe.com
Try Our Full Platform: backtobackswe.com/pricing
📹 Intuitive Video Explanations
🏃 Run Code As You Learn
💾 Save Progress
❓New Unseen Questions
🔎 Get All Solutions
First, we must ask what asymptotic means. Well, you have probably heard of the word "asymptote".
An asymptote is a "line that continually approaches a given curve but does not meet it at any finite distance".
Therefore, asymptotic analysis is the analysis of tail behaviors not reaching any finite point. It is a method of describing limiting behavior.
Wall Time vs. Asymptotic Complexity
Well...why not just measure the seconds our code takes to run? And get the Elapsed real time (wall time)?...like Leetcode.
So why do we care about this...well in computer science we often deal with problems that are at a grand scale with inputs to the order of millions and billions.
And thus, the true measure of the efficiency of an algorithm is best expressed in its tail behavior on very large input. It only then shows its true colors.
An Expression of Asymptotic Behaviour
Insertion Sort: 2 * n^2
Merge Sort: 50 * n * log(n)
We have 2 computers:
Computer A: runs 10 Billion instructions / second
Computer B: runs 10 Million instructions / second
Computer A is 1000x faster than Computer B
Computer A runs insertion sort, Computer B runs merge sort
How long will each computer take to sort 10 million numbers?
Computer A: 5.5 hours
Computer B: 20 minutes
A computer that runs 1000x faster lost horrendously to a computer that runs 1000x slower than it.
But the thing is that insertion sort will be faster for an initial amount, but it will lose as the input gets larger (and that's what we care about and what is a true expression of its efficiency).
++++++++++++++++++++++++++++++++++++++++++++++++++
HackerRank: kzfaq.info/love/Of7UPMHBjAavgD0Qw5q5ww
Tuschar Roy: kzfaq.info
GeeksForGeeks: kzfaq.info/love/0RhatS1pyxInC00YKjjBqQ
Jarvis Johnson: kzfaq.info
Success In Tech: kzfaq.info/love/-vYrOAmtrx9sBzJAf3x_xw