Asymptotic bounding or Asymptotic analysis

In this article, we will be discussing what is asymptotic bounding or asymptotic behavior, why is it important to do asymptotic analysis with an example.

Prerequisites:

Basic understanding of graphs and basic time complexity understanding is required.

What is asymptotic bounding or asymptotic behavior:

Asymptotic behavior in simple terms can be defined as “How does an algorithm behave when large values of input is used”. The true understanding of the behavior of an algorithm can be achieved when tested at the tail end.

An asymptote is a straight line that continually approaches a given curve but does not meet it at any finite distance.

For example in the equation y=1/x, as x tends to infinity y tends to 0. It means, as the value of x increases, the value of y decreases. The graph for this equation can be represented as below, as the value of x is increasing the value of y can be seen getting smaller and smaller.

Input given to the graph,

x	y
1	1
2	0.5
3	0.333333
4	0.25
5	0.2
10	0.1
20	0.05
30	0.033333
50	0.02
100	0.01

Why do we need to understand asymptotic bounding?

Consider Computer A runs the slower algorithm, at the rate of 10000000 instructions/sec and Computer B runs the faster algorithm at the rate of 10000 instructions/sec.

Computer A takes 5hours to run the slower algorithm even if the rate at which is executes the instructions is faster whereas Computer B takes 20minutes to run the faster algorithm even if the rate at which it executes the instructions is slower.

Why did the slower algorithm loose on Computer A which is 1000 times faster than Computer B? To understand this we need to do asymptotic analysis.

Consider below table and graph which represents linear time O(n),

x	y=x/2	y=x	y=2x
0	0	0	0
2	1	2	4
4	2	4	8
6	3	6	12
8	4	8	16

If you see the above graph, all the equations behave in the same way as the value of x is increased. Graphs y=x/2, y=x, y=2x shows linear time behavior when plotted for large values of input x.

The above graph represents a class of functions that behave linearly. Hence the constants in equations y= (1/2)x, y=(1)x, y=(2)x are not very important and can be ignored because all the equations show similar behavior when tested for larger values.

In the next post I will be discussing the different asymptotic notations used to represent the running time of an algorithm.

Please like and share if you find this blog post useful. Your feedback is highly appreciated.