Can anyone help me analyze the run time of the following pseudocode
for(i = 0; i < n*n*n; i++)
for(j = i; j < n; j++)
x++
The way I see it's omega(n^3) for the lower bound, since that's what it would be if inside the outer for-loop was just theta(1).
I'm getting confused by the inner loop that only runs for the first n iterations of the outer loop. Do I just average the run-time of the inside loop: n^3 * ((1/n^2)*n + (1/n)*1, in which case it's O(n^3)?
Depends how smart your compiler is. The algorithms can be split into two parts (this may have off by one errors, but you get the idea)
// i<n
// O(n^2)
for( i=0; i<n ; ++i )
for( j=i; j<n; ++j )
x++
// n < i < n*n*n
// O(n^3)
for( i=n ; i<n*n*n; ++j)
noop(); //do nothing
For i > n the second part does nothing, so a smart compiler will only loop i to n,
in which case it is O(n^2).
However if your compiler isn't smart the latter half will execute too and you will just get an O(1) comparison and so overall behaviour is O(n^3).