Exercise 5 Theory: Running time analysis

Exercise 1:

Put in the missing word/phrase (...)
Note that the upper/lower limits is true for n >= n0 where n0 is a constant.

a) An algorithm with running time O(f(n)), means that the running time has a/an ... limit.
1) upper
2) lower
3) upper and lower

b) An algorithm with running time Theta(f(n)), means that the running time has a/an ... limit.
1) upper
2) lower
3) upper and lower

c) An algorithm with running time Omega(f(n)), means that the running time has a/an ... limit.
1) upper
2) lower
3) upper and lower

Exercise 2:

This exercise is about intuitive understanding of the running time of traversing different data structures.

State all answers with the asymptotic notation that gives most information. I.e. the most running times is O(n^n), since
this is a very high upper limit, but Theta(f(n)) states both lower and upper limit, and so gives much
more information.

a) What is the running time of traversing a linked list with n different elements?
1) Theta(1)
2) Theta(log n)
3) Theta(n)
4) Theta(n^2)
5) Theta(n^3)

b) What is the running time of traversing a linked list with on billion elements?
1) Theta(1000000000)
2) Theta(1)
3) Theta(n)
4) Theta(n log n)
5) Theta(n^2)
6) Theta(n^1000000000)

c) What is the running time of traversing a matrix with n rows and n columns?
1) Theta(1)
2) Theta(log n)
3) Theta(n)
4) Theta(n log n)
5) Theta(n^2)
6) Theta(n^3)

d) What is the running time of traversing a datastructure formed as the first layer of a pyramid of balls (see the figure), where n=number of
rows?

(Text underneath the figure: Bottom layaer of the pyramid, where n=number of rows, and number of balls = 1 + 2 + ... + n)

1) Theta(n log n)
2) Theta(n * sqrt(n)), where sqrt=square root
3) Theta(n^2)
4) Theta(n^2*log n)
5) Theta(n^3)
6) Theta(n^4)

e) What is the running time of traversing a datastructure formed as a pyramid (see the picture) with height n?

1) Theta(n log n)
2) Theta(n^2)
3) Theta(n^2 * log n)
4) Theta(n^2 * sqrt(n)), where sqrt=square root
5) Theta(n^3)
6) Theta(n^4)

f) What is the running time of an algorithm which at iteration i does i^2 operations? The algorithm makes n iterations.

1) Theta(n log n)
2) Theta(n^2)
3) Theta(n^2 * log n)
4) Theta(n^2 * sqrt(n)), where sqrt=square root
5) Theta(n^3)
6) Theta(n^4)

Exercise 3:

This exercise is about the substitution method solving recurrences.
Given the recurrence

T(n) = 2401T(n/7) + n^3
T(1) = 1

If we wanted to use the substitution method and we assumed that:
T(n/2) <= c * n^2/4 * log(n/2)

a) What are we hoping to prove?

1) That we can find a lower asymptotic limit for the recurrence
2) That T(n) <= c * n^2/4 * log(n/2)
3) That T(n) <= c * n * log(n)
4) That T(n) <= c * n^2 * log(n)

b) If you use the master-theorem on this recurrence, which case does it belong to in Cormen (3. edition)?

1) Case 1
2) Case 2
3) Case 3
4) None of them

c) What is the running time? (you choose method)

1) Theta(n)
2) Theta(n log n)
3) Theta(n^2)
4) Theta(n^3)
5) Theta(n^4)

d) If we exchange n^3 with n^5 which case will we be in if we use the master-theorem?

1) Case 1
2) Case 2
3) Case 3
4) None of them

Exercise 4:

This exercise is about exchange of variables. Note that n^1/2 = square root of n.

a) Solve the recurrence given by: T(n) = T(n^1/2) + 1

1) Theta(lg n)
2) Theta(lg lg n)
3) Theta(lg n lg lg n)
4) Theta(lg lg n lg lg n)

Exercise 5:

This exercise is about recursion trees. These can be used as a helping tool to guess a solution for the substitution method. Every node in a recursion tree represents a cost. I the figure
below there is an example for the recurrence T(n) = 2T(n/2) + n, with T(1) = 1.

(figure)

Note that the recursion tree has ben drawn step by stepp and that the whole tree is not drawn. It is wise to draw the tree step by step to manage to see how it goes on. In the tree above we see that the internal cost in every
node will be n/2^i where i is the level the node is present at (0-index).

The level of the leaf nodes is found by solving n/2^i = 1:
log2 2^i = log2 n
i * log2 2 = log2 n
i = log2 n
Number of nodes on each level is thus 2^i. And number of leaf nodes is 2^log2 n = n

a) Given the recurrence T(n) = T(n/3) + T(n/2) + n, T(1) = 1. What is the height of the recurrence tree?

1) Theta(n * log n)
2) Theta(log3 n + 1)
3) Theta(log6 n + 1)
4) Theta(log n)
5) log3/2 n + 1

Exercise 6:

The function gjoerNoe() has the running time Theta(1).

def f1(i):
	gjoerNoe()
	if i <= 1:
		return
	f1(i // 2)
	f2(i - 2)

def f2(i):
	gjoerNoe()
	if i <= 1:
		return
	f1(i // 2)

a) What is the running time of f1(n)? (Hint: Do not try to calculate this exact.)

1) Theta(log(log(n)))
2) Theta(log n)
3) Theta(sqrt(n)) where sqrt=square root
4) Theta(n)
5) Theta(n * log n)
6) Theta(n * sqrt(n)) where sqrt=square root
7) Theta(n^2)
8) None of the alternatives is correct.

Exercise 7:

In this exercise you are going to analyse the running time for small functions. The function gjorNoe(n) has the running time Theta(n).

a)

def funksjon1(n):
	if n > 0:
		funksjon1(n - 42)
		funksjon1(42)
	gjorNoe(42)

1) T(n) = O(1)
2) T(n) = O(n)
3) T(n) = O(log n)
4) T(n) = O(n * log n)
5) T(n) = O(n^2)
6) T(n) = O(n^3)
7) T(n) = O(2^n)
8) It will never stop

b)

def funksjon2(n):
	gjoerNoe(n)
	if n >= 1:
		funksjon2(n//3)
		funksjon2(2*n//3)

1) T(n) = O(1)
2) T(n) = O(n)
3) T(n) = O(log n)
4) T(n) = O(n * log n)
5) T(n) = O(n^2)
6) T(n) = O(n^3)
7) T(n) = O(2^n)
8) It will never stop

c)

def funksjon3(n):
	gjoerNoe(n//6)
	if n > 0:
		funksjon3(n/2 - 2)
		funksjon3(n/2 - 3)

1) T(n) = O(1)
2) T(n) = O(n)
3) T(n) = O(log n)
4) T(n) = O(n log n)
5) T(n) = O(n^2)
6) T(n) = O(n^3)
7) T(n) = O(2^n)
8) It will never stop