Understanding Asymptotic Analysis and Notation

Free 5-Day Mini-Course: https://backtobackswe.com
Try Our Full Platform: https://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: https://www.youtube.com/channel/UCOf7UPMHBjAavgD0Qw5q5ww

Tuschar Roy: https://www.youtube.com/user/tusharroy2525

GeeksForGeeks: https://www.youtube.com/channel/UC0RhatS1pyxInC00YKjjBqQ

Jarvis Johnson: https://www.youtube.com/user/VSympathyV

Success In Tech: https://www.youtube.com/channel/UC-vYrOAmtrx9sBzJAf3x_xw