Finding Time Complexity of these two algorithms?

Question

Here's the first algorithm,

sum = 0;
for( i=1; i<n; i++ )
        for( j=0; j<i*n; j++ )
            for( k=0; k<j; k++)
            sum++;

Here's the second algorithm

sum = 0;
for( i=1; i<n; i++ )
    ( j=1; j<i*n; j++ )
        if( j%1 == 0 )
            for( k=0; k<j; k++ )
                sum++;

Can anyone help me finding the Big O for these two algorithms? I tried doing it and I got n^5 but when I checked it by comparing the running times of an algorithm of n^5 and these algorithms, there was a huge difference... Although both of these algorithms had more or less equal running times, which mean their time complexity is same.

If anyone can then please provide a possible way to analyze these two algorithms and to find the time complexities of both. Thank you

Note: I have also tried comparing it with algorithms of n^4 time and there still was a huge difference between the running times... I can provide the values also of the running times of all these different algorithms if required.

What exactly do you mean by "huge difference"? Any constant factor would be ok. — MrSmith42
"if( j%1 == 0 )" is useless, its always true. So these two are actually same. — User_67128
@MrSmith42 I'm not talking about their Time Complexities... I actually implemented these algorithms in C++ Compiler and calculated the CPU Running times for different input sizes (like 5, 10, 15 etc) for these algorithms. The running times of these 2 algorithms mentioned were almost same. Then I used an algorithm of which I was sure that it is of O (n^5) time complexity and got CPU running times for that algorithm for the same input sizes. But the results I got were nowhere close to the ones I got from these 2 algorithms. However, my doubt has been cleared now and I know why they werent same — Hassan Ashas

OmG OmG · Accepted Answer · 2020-02-19T14:29:58

The time complextiy for the first algorithm is like the following sum:

sum_{i=1}^{n-1} sum_{j=1}^{i*n} j =
sum_{i=1}^{n-1} i * n * (i*n + 1) / 2 = 
0.5 * sum_{i=1}^{n-1} i^2 * n^2 + i*n = 
0.5 * (n^2 * sum_{i=1}^{n-1} i^2 + n * sum_{i=1}^{n-1} i) = 
0.5 * (n^2 * \Theta(n^3) + n * \Theta(n^2)) = \Theta(n^5)

So, you are right. But be careful that this is the asymptotic time complexity and can be different from the measured CPU running time.

And it is the same for the second algorithm (with a tiny difference), as always, j%1 is equal to zero for all j > 0.

Finding Time Complexity of these two algorithms?

1 Answers