Approximate run time

Question

I have written a program in C to solve the maximum sub-array problem. This solution is of O(N^3) complexity. Is there any way to approximate the run time for N = 1,000,000? I know there are much faster algorithms than that of third order but I need to compare those to my current program.

int MaxSubSlow(){
    int max_so_far = 0,i,j,k,temp_sum;


    for(j=1;j<N;j++){   
        for(k=j;k<N;k++){
            temp_sum = 0;
            for(i=j;i<k;i++){
                temp_sum += A[i];
            }   
            if(temp_sum > max_so_far){
                max_so_far = temp_sum;      
            }
        }
    }


    return max_so_far;
}

Yes, i wanted to make it easier to read but apparently, it is more confusing that way. I will edit it out. — Shivalnu, Mar 08 '17 at 17:24
Duplicate of: http://stackoverflow.com/questions/3255/big-o-how-do-you-calculate-approximate-it — Jason R. Mick, Mar 08 '17 at 17:26
Possible duplicate of [Big O, how do you calculate/approximate it?](http://stackoverflow.com/questions/3255/big-o-how-do-you-calculate-approximate-it) — Jason R. Mick, Mar 08 '17 at 17:26
My question is not about calculating the order of the algorithm. I know it is O(N^3). My question is if i can calculate the time it would take to run for N =1000000 — Shivalnu, Mar 08 '17 at 17:28

Thomas Padron-McCarthy · Accepted Answer · 2017-07-02T23:48:07.360

1

If it is O(N^3) you can approximate N=1,000,000 by running it with N=1,000 and then multiply by 1,000,000,000. (But, since the O notation can hide other significant terms except the N^3 one, you can't be sure that it is a very good approximation.)

edited Jul 02 '17 at 23:48

answered Mar 08 '17 at 17:34

Thomas Padron-McCarthy

27,232
8
51
75

Approximate run time

1 Answers1