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.

Answer 1

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.