Asymptotic Analysis

In algorithm analysis, the most general problem that is faced is that different algorithms to be compared work on different hardwares having entirely varied platforms. Hence, its very difficult to compare.

This problem at hand is solved by using the idea of asymptotic analysis. The idea behind the same is as follows –

1) Look at the growth of running time that is T(n) rather than n itself.

2) Ignore machine dependent constants.

As a result of the above, this analysis can be used for comparing both relative and absolute speeds irrespective of the platforms. Thus, asymptotic analysis is a vital concept which is a bigger picture of the comparison rather than a closer lookup of the same.

For example consider –

1) Algorithm 1 having a Theta(n^3)

2) Algorithm 2 having a Theta(n^2)

So for n -> infinity, Theta(n^2) is always going to be faster than Theta(n^3), no matter even if we run algorithm 2 on a slower computer and algorithm 1 on a faster one.

So, we see how using Theta notation of asymptotic analysis enables us to compare two algorithms irrespective of platforms.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s