Thursday, 10 March 2016

Time complexity

So what do you mean by time complexity ???

Have you ever wondered why sometimes when you sub,it your code and the online judge gives you an error named TLE (Time Limit Error) ? This is what i am going to explain to you .
Its a simple way of measuring how much time your code or algorithm  is taking to output the result as  per the given input . The time complexity of algorithms is most commonly expressed using the big O notation.
Time Complexity is most commonly estimated by counting the number of elementary functions performed by the algorithm. And since the algorithm's performance may vary with different types of input data, hence for an algorithm we usually use the worst-case Time complexity of an algorithm because that is the maximum time taken for any input size. 

How do we measure it ?? 
While measuring the time complexity of a code , we don't consider the time taken by constants , or variable declaration as they very very less time as  compared to the whole program .
suppose part of a code is :
for(i=1 ; i <=n; i++ )
{
      statement ;
}
this statement will run N times . one time for each value of 'i' 
therefore this part of code will have a time complexity of O(n) .
We try to reduce time complexity of our code as much less as possible. For this we try to use better algorithms , alternate methods of input . Whenever stuck try to google alternate methods of the problem where you are stuck
There are some other time complexities such as O(log(n)) (in trees ) , O(nlog(n)) , O(n^2) (using 2 nested for loops) e.t.c .

So the main aim of every programmer is to reduce the time complexity so as to give a High performance of your code . 

No comments:

Post a Comment