Time taken by codes to run...

Hi,…how can i find the runtime of my program in c++ ??

To find the runtime of your program, you’re going to have to do a little math.

First, you have to be familiar with the problem’s constraints. Look at the problem statement to figure this out.

Then, look at your program and figure out what loops there are. When loops are nested (that is, they are inside one another), you have to multiply the maximum number of times it could be executed. If they are in series (that is, one after another) you have to add the maximum number of times it could be executed.

For example, suppose the constraint for some problem is N <= 100, and your program is something like this.

for( int i = 0; i < N; i++ ) {

    for( int j = 0; j < N; j++ ) {
       // Do stuff.
    }
}

Since these loops are nested, you have to multiply the maximum number of times these loops could be iterated. The outermost loop is executed N times, which the problem said could be at most 100. The innermost loop is also executed N times. So, this combination will take 100 * 100 iterations = 10000 total iterations.

What if we had this?

for( int i = 0; i < N; i++ ) {

    for( int j = 0; j < 1; j++ ) {
    // Stuff.
}

This should also be 10000, right? No. The innermost loop always executes 1 time. So, you would multiply 100 from the outermost loop and 1 from the innermost loop to get a total iteration number of 100. (Don’t make this mistake. It’s a very common one.).

Now what if we have something like bubble sort with loops like this?

for( int i = 0; i < N; i++ ) {

  for( int j = i + 1; j < N; j++ ) {
  // Stuff.
  }
}

This is where basic combinatorics knowledge is handy. Think about it a little. How many times does the innermost loop iterate during the first iteration of the outermost loop? N-1. What about the second iteration? N-2. See a pattern? Add all these up and you get a running time of N(N+1)/2 (basic series formula), which is O(N^2). (If you’re not familiar with Big-O notation, please read this http://activities.tjhsst.edu/sct/lectures/1112/complexity102111.pdf ).

Now, suppose these for-loops were in series.

for( int i = 0; i < N; i++ ) {
// Stuff.
}

for( int i = 0; i < N; i++ ) {
// Stuff.
}

The first for-loop iterates N times, which can be 100. The second loop iterates N times as well. Since these are in series, you would add 100 + 100 to get 200 iterations.

How is the number of iterations important? Well, typical computers can perform 1E8 iterations per second (1E9 if you’re working with a supercomputer. Unfortunately, you aren’t with CodeChef). Take the number of iterations your program takes, divide it by 1E8, and now you have the amount of time your program will take in the worst-case scenario :D.

Now, this only works with programs without recursion. What about with recursion?

Calculating the running time of a program involving recursion is a little less accurate. You have to construct a recursion tree. If you don’t know what a recursion tree is, feel free to google it. It’s not a terribly complicated concept.

Your job with the recursion tree is to find out the number of leaves on the tree. To do this, you have to take the number of children for each node and take that raised to the kth power where k is the height of the recursion tree. So, if your recursion tree happens to be a binary tree, your “iterations” per se will be 2^k where k is the height of the tree. If each node has 3 children, you would do 3^k

The problem with the above method for recursion is that you do not always recurse in a uniform way (some nodes have 2 children, some have 4, etc.). I do not have a way to calculate this exactly, so I just make the base equal to a number that sounds appropriate for the problem.

Now what if I have something like a while loop or a do/while loop? There’s no systematic way to solve this that I know of. In general, it’s a probability thing. You have to intuitively decide what the worst case is and figure out the number of times that loop iterates.

Do I really have to analyze EVERY loop in my program? Generally, no. Why? We don’t have the time to do it usually, and sometimes we don’t even have the attention span. As a substitute, we only analyze the portion of the program executed most (most number of nested loops, most recursion, etc).

The above methodology works well with many programming contests. However, with CodeChef I’ve noticed that they do not push the boundaries on the inputs they use. So, if you calculate something that goes a bit above the time limit, it might still work. The only way to make sure is to try it out.

Now that I think about, I encourage you to read the article I gave earlier in this post even if you are familiar with Big-O notation. It seems to be very helpful.

6 Likes

#include
#include
using namespace std;

int main()
{
    clock_t t1,t2;
    t1=clock();
    //code goes here
    t2=clock();
    float diff ((float)t2-(float)t1);
    float seconds=diff/CLOCK_PER_SEC;
    cout<<sec<<endl;
    system ("pause");
    return 0;
    
}

try this code in your program and it will give u time elpased in seconds… n yup before you do that make sure you learn about complexity as well as suggested by @kullalok. enjoy happy coding

3 Likes