Week 3

Question 1

What is the complexity of the following function?

int temp = 0;
for (i = 0; i < n; i++) {
	for (j = n; j > i; j--) {
		temp = temp + i + j;
	}
}

Answer 1

O(n^2)

Always worst case.
In this code snippet, we have two nested for loops, each of which execute a number of times that is dependent on n.

Question 2

Determine the most appropriate run-time for the following algorithm. Write out your answer in expression form (just include the expression within the “O()” notation in your response).

for (int i = 0; i < n; i++) {
    // do something O(1)
}
for (int j = m; j > 0; j--) {
    for (int k=0; k < n; k++) {
        if (k > j) {
            //do something O(1)
        }
    }
}

Answer 2

O(m*n)

Question 3

Determine the most appropriate run-time for the following algorithm. Write out your answer in expression form (just include the expression within the “O()” notation in your response).

for (int i = 0; i < n*n; i = i+10) {
    // do something O(1)
}

Answer 3

n^2

+10 like (1/10) faktor

Question 4

Determine the most appropriate run-time for the following algorithm. Write out your answer in expression form (just include the expression within the “O()” notation in your response).

public int method(int n) {
if (n==0) return 1;
return n * method(n-1);
}

Answer 4

O(n)

There is one recursive call in this method. The method decrements by 1 in each call to itself until it reaches 0. The method itself performs constant time operations (e.g. decrementing by 1, returning 1).

The method will run n times performing O(1)operations within the method (outside of the recursive call), so the overall run-time evaluates to O(n).