i := n;
WHILE i > 1
FOR j := i to n DO
X;
END
FOR j := 3*i to 3*n DO
X;
END
DEC(i); (* i decrement *)
END
For this pseudocode, I have to calculate a function f: N -> N, depending on n. I'm doing something like this for the first time, so I don't even know if my approach is correct. So, in the first line I have 1 constant time. The while loop runs n-1 times + n times comparison and n-1 constant time for decrement. The first for loop runs n-i+1 times. The second for loop runs 3n-3i+1 times. So (I think) that would be the formula: f(n)=1+((n-1)+n+(n-1))*((n-i+1)+(3n-3i+1)) and that would be f(n)=12n^2 -12ni -2n +8i -3
But now I have n and i variables? How do I get rid of the i?
Let's suppose that "to n" means "the last value is n-1" (it is not important in terms of time complexity - see the final explanation).
Let's take f(X) = the time complexity to run X.
The total amount of time is:
1 +
0 + 0 + // i=n
f(X) + 3*f(X) + // i=n-1
2*f(X) + 6*f(X) + // i=n-2
3*f(X) + 9*f(X) + // i=n-3
...
(n-2)*f(X) + 3*(n-2)*f(X) // i=2
------------------------------
1 + 4*f(X) + 8*f(X) + 12*f(X) + ... + 4*(n-2)*f(X)
And this sum is equal to:
1 + 4*f(X)*(1+2+3+...+n-2) = 1 + 4*f(X)*(n-2)*(n-1)/2
But the constants don't influence the trend for that function => the result is:
O(2*f(X)*(n-2)(n-1)) = O(f(X)*(n^2))
which is O(n^2) if X is just a simple operation (O(1)).
P.S.:
If you are not sure that the constants doesn't influence the final result, just try to calculate:
1 + 4*f(X)*(n-2)*(n-1)/2
lim ---------------------------
n->infinite f(X)*n^2
and you'll obtain a finite number (it means that the numerator and the denominator are similar).