Can anyone help me finding the Time Complexity of these two algorithms?

Here are the two algorithms,

1
2
3
4
5
sum = 0;
	for( i=1; i<n; i++ )
			for( j=0; j<i*n; j++ )
			    for( k=0; k<j; k++)
				sum++;		


and second one is,

1
2
3
4
5
6
7
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 you can find the time complexity of both of these then please help and also tell how did you manage to get to the time complexity. Thank you!
The i loop runs O(n) times.
For each of these, the j loop runs O(n2) times, making O(n3) times.
For each of these the k loop runs O(n2) times, making O(n5) times.

So, I think it is O(n5) - same as you.



The line
if( j%1 == 0 )
always produces true, so I'm not surprised they have about the same run time!



but when I checked it by comparing the running times of an algorithm of n^5 and these algorithms

Yeah, but there's quite a big difference (factor of 100) between 0.1n5 and 10n5 ... yet they are both O(n5)

The complexity describes how one particular algorithm's run time varies with n ... not how it will compare with another algorithm of the same theoretical complexity.


Plot log(run time) against log n for large n and look at the gradient - if it tends to linear then you have that power law complexity.



Last edited on
break it down.
the top one, take out the inner loop. what is it for just that much?
for 1 to n, you do it n times, that is, if n is 5 …
for 1, for 5
+ for 2, for 10
+ for 3, for 15
+ for 4, for 20

what is that going to become?
then add the inner loop back once you get the outer piece of it figured out...

Lastchance makes a good point. wall clock time and complexity are only roughly related. A poorly written O(n) can take more wall clock than a slick O(n*n). that if statement may be slowing you down (comparisons cost and are often forgotten) without saving you anything. To compare wall clock, it really needs to be the same work done (same output). You have that here because the if did not do anything, but keep that in mind later.
Here, at the if level, if the compiler does not know that %1 is a special case and it does the work, you have added the two outer loops worth of work again, not doubling the work done, but adding a fair amount.
Last edited on
Got it. Thanks a lot!
Really appreciate the help :)
Topic archived. No new replies allowed.