Calculating Compexity

general
1

Hi everyone
I want to ask a question because I am getting TLE in a problem.

How can I calculate the complexity and minimize the time taken by my code.

2

You can look at this.Generally there may be an Algorithm for the problem you are trying which can reduce you execution time.

3

hope… this would help you…
https://discuss.codechef.com/questions/7585/why-do-i-get-a-time-limit-exceeded?page=1#7586

4

For calculating the complexity of an algorithm you must know about asymptotic analysis of algorithms, Big-O Notation and their worst case ( or sometime average ) running times.

This is really a time saver if you forget the time complexity of operations of different data structures.

The following links may help on calculating the complexity of your algo Time Complexity Calculation, Introduction to Algorithmic Complexity Analysis,
Analysis of Algorithms Link 2 You will find plenty of articles on the internet regarding analysis of algorithms!

But in context of competitive programming, you should always remember that normal judges (like CodeChef, Codeforces) can handle 10^8 - 10^9 operations per second and generally the time limit is 1 second. This may also help in this context.

1 Like
5

Thanks to all of you @coder_voder @dragon96 @nikhil_chandak These are really helpful answers for beginners like me.

6

I think this is helpful to you @only4

This is an excellent article : http://www.daniweb.com/software-development/computer-science/threads/13488/time-complexity-of-algorithm

The below answer is copied from above (in case the excellent link goes bust)

The most common metric for calculating time complexity is Big O notation. This removes all constant factors so that the running time can be estimated in relation to N as N approaches infinity. In general you can think of it like this:

statement;
Is constant. The running time of the statement will not change in relation to N.

for ( i = 0; i < N; i++ )
statement;
Is linear. The running time of the loop is directly proportional to N. When N doubles, so does the running time.

for ( i = 0; i < N; i++ ) {
for ( j = 0; j < N; j++ )
statement;
}
Is quadratic. The running time of the two loops is proportional to the square of N. When N doubles, the running time increases by N * N.

while ( low <= high ) {
mid = ( low + high ) / 2;
if ( target < list[mid] )
high = mid - 1;
else if ( target > list[mid] )
low = mid + 1;
else break;
}
Is logarithmic. The running time of the algorithm is proportional to the number of times N can be divided by 2. This is because the algorithm divides the working area in half with each iteration.

void quicksort ( int list[], int left, int right )
{
int pivot = partition ( list, left, right );
quicksort ( list, left, pivot - 1 );
quicksort ( list, pivot + 1, right );
}
Is N * log ( N ). The running time consists of N loops (iterative or recursive) that are logarithmic, thus the algorithm is a combination of linear and logarithmic.

In general, doing something with every item in one dimension is linear, doing something with every item in two dimensions is quadratic, and dividing the working area in half is logarithmic. There are other Big O measures such as cubic, exponential, and square root, but they’re not nearly as common. Big O notation is described as O ( ) where is the measure. The quicksort algorithm would be described as O ( N * log ( N ) ).

1 Like