Asymptotic Notation–In a mathematical way

 

“A simplified way to calculate the running time of an algorithm. The primitive way is to count the number of iterations, instructions and their constant running time on the machine. But tracking the running time on all the machine is impossible. Instead we can use Asymptotic Notation to eliminate constant “

Metaphor

  The time taken to do some thing is really important these days. Not just time, even the resource usage is important nowadays. To calculate how much resource/time is taken to do a job, there are many statistical ways. These statistical ways are needed for a computer algorithm as well.

Concept

  Consider, your whole algorithm can be represented as a function f(n). Where n is the input size. We need to calculate the running time f(n). How can we do this? Take the constant time taken on a machine as “c”. Up to certain input values, running time will be proportional to the input size. The running time is represented with a separate function named g(n). Usually, it gets multiplied like c.g(n). This “c” value is never taken into account and a inequality is created for avoiding it.

There are three inequalities possible for f(n) = c.g(n) (note that this equality is possible only for a some n, as always running time increases with input size and type of input)

• O(worst case): f(n) <= [g(n)]: Upper bound running time considering input size->infinity. Here, we consider largest running time possible for some input size. Note that, f(n) is the function which takes n size input, and g(n) is the time taken to run f(n), for n being the size of input.
• Ω(best case): f(n) >= [g(n)]: Lower bound running time considering f(n) runs in best case. Here, we treat running time is smaller for some input size. This considers the lowest running time possible for some input.
• Θ(average case): 0 <= f(n) >= [g(n)]: Average/Ranged running time vs input size.  This is a average running time case between above two notations.

The above notations are called Big-Oh, Big-Omega and Big-Theta respectively. For most of the algorithms, they ask only Big-Oh case. Read more about how to determine this value here: http://rob-bell.net/2009/06/a-beginners-guide-to-big-o-notation/

Important points

• The same notation can be used to represent space vs input size as well
• Upper bound, Lower bound, middle range: makes it clear that, upper bound covers all the iterations of an algorithm for the full input set. Lower bound only covers the best case input set and Average case covers a median.
• Read more about Asymptote here: http://en.wikipedia.org/wiki/Asymptote. Its a tangent which is parallel to the infinitely running curve.
• Remember drawing tangents in an asymptotic circular graph sheet? :) That is the math behind these notations which basically represents the infinite/generic function for an algorithm.
• There is something called, Little-Oh, Little-Omega and Little-Theta. They consider constant value strictly while Big notations ignore it considering g(n) is sufficiently large to ignore “c”.
• I think this post became a pure mathematical post. As i said, we need to study multiplication tables from 1st grade to do this perfectly.. ;)