The purpose of this hand-in is for you to get a better idea of what the performance of different complexity classes is (part 1) and some practice calculating complexities of different functions (part 2).
In this part you are given the runtime \(T(n)\) of several hypothetical algorithms. The algorithm takes a certain amount of time for an input of size 100. Calculate how much longer (the ratio) the algorithm will take when the input size is a) 101, b) 200, c) 10000, and finally d) assuming that \(T(n)\) is the runtime measured in seconds, what is the biggest problem it can solve within 100000 seconds (a day and a bit)? One of the answers is already filled in to help you start.
In this part you will calculate the complexities of ten functions. Although they are toy functions, the techniques you use are just the same as for realistic functions.
For ex1
to ex5
, you should first write down a mathematical function \(T(n)\) that counts exactly how many times the line sum += 1
is executed. ex2
is solved for you already. For ex6
to ex10
you should write a recurrence relation for \(T(n)\) which may use Big-Oh notation. You should then write down the complexity of each function.
You may assume that n
is a power of two if it helps.
int ex2(int n) {
int sum = 0;
for (int i = 0; i < n; i++)
for (int j = 1; j < n; j++)
sum += 1;
return sum;
}
Answer:
n
times.i
, inner loop runs n-1
times (from 1 to n-1
).int ex3(int n) {
int sum = 0;
for (int i = 0; i < n; i++)
sum += 1;
for (int j = 1; j < n; j++)
sum += 1;
return sum;
}
int ex4(int n) {
int sum = 0;
for (int i = 1; i <= n; i *= 2)
for (int j = 0; j < n*n; j++)
sum += 1;
return sum;
}
int ex5(int n) {
int sum = 0;
for (int i = 0; i < n; i++)
for (int j = 0; j < i; j++)
sum += 1;
for (int k = 0; k < n; k++)
sum += 1;
return sum;
}
int ex7(int n) {
int sum = 0;
for (int i = 0; i < n; i++)
sum += 1;
if (n > 0)
return sum + ex7(n-1);
else
return 0;
}