running time of algorithm

[aliceeeeeeeeee]

I'm not exactly sure how to come up with a function for the running time of an algorithm...
In class, we found the upper bound of the following to be n((nx+y) + z) + w where nx+y is lines 5-7, z is lines 2-4 and 8-9, and w is the final exit.
(I know it's not in python...)

Quote:

IS (int[] A) {
....int i = 1
....while (i < A.length()) {
........t = A[i];
........int j = i;
........while (j > 0 && A[j-1] > t) {
............A[j] = A[j-1];
............j = j - 1;
........}
........A[j] = t
........i = i + 1
....}
}

I can see how that equation was come up with but I don't know how to find something similar for this:

Quote:

if A[0][0] < -100 or A[0][0] > 100:
....for i in range(n):
........for j in range(n):
............for k in range(j):
................for p in range(i):
....................C[i][j] = (i + j)*A[i][j] + (k + p)*B[k][j]
else:
....for i in range(n):
........for j in range(n):
............for k in range(j):
................C[i][j] = (i + j)*A[i][j] + k*B[k][j]

Please help

[Brightguy]

Which part are you having trouble with? The simplest thing to do is to consider what happens in the worst-case scenario. In this case, that would be when the conditional is true.

It also depends on how precise you want your analysis to be. The crudest bound would be O(r^4) arithmetic operations where r = max|range(i)|.

[aliceeeeeeeeee]

I need to derive the upper bound on the asymptotic complexity of it as a function of n and write the total number of multiplications as a function of f(n)

[Brightguy]

aliceeeeeeeeee @ Fri Apr 06, 2012 11:48 pm wrote:

I need to derive the upper bound on the asymptotic complexity

Well, an upper bound; there will not be just one.

Since you're looking for an upper bound, the simplest way is to look at both branches of the if/else and ask: which branch has a worse computation time? Then perform your analysis using that branch only.

I see now that range is a built-in Python function with range(i) = [0, 1, ..., i−1]. Using that you should be able to come up with an expression for the cost of the loops.