Important Information: Throughout this exam paper log() denotes the binary logarithm,i.e, log(n) = log2(n). We also write log log n as an abbreviation for log(log(n)), and logc nas an abbreviation for (log n)c .As in the lectures, arrays start at index 0. For example, an array A of length n consistsof the elements A[0], A[1], ... , A[n − 1].Q1. This question is about Big-O notation and loop invariants.(a) For each of the following statements, mark in the answer sheets whether thestatement is true or false.1. 5 ∈ Ω(n)2. log n /∈ O(n2)3. 2n ∈ O(log n)[3 marks](b) What is the smallest integer n0 such that, for every n ≥ n0, the inequality12n2 ≥ 16nholds? Give your answer in the answer sheets.[3 marks](c) Order the following sets so that each is a subset of the one that comes after it:(1) O(log n) (2) O(log log n) (3) O(2n) (4) O(√n)Give your answer in the answer sheets in form of a permutation of the num-bers 1, 2, 3, 4 (write exactly one digit in each box). For example, the permutation2, 3, 1, 4 corresponds to the orderingO(log log n) ⊆ O(2n) ⊆ O(log n) ⊆ O(√n) .[3 marks]Q2. This question is about sorting.(a) For each of the following statements, mark in the answer sheets whether thestatement is true or false.1. Insertionsort is a dynamic programming algorithm.2. The recursion tree of a run of Mergesort on an instance of size n has a depthof O(log n).[2 marks](b) For the following input to Insertionsort, state the runtime of the algorithm usingΘ(.)-notation in the answer sheets (as usual, the objective is to sort in increasingorder):Integer array A of length n with A[i] = n − i for every 0 ≤ i ≤ n − 1.[2 marks]Page 2 of 4MOCK EXAMQ3. This question concerns algorithmic design principles and recurrences.(a) Determine the runtime of Algorithm 1 using Big “Theta” notation. Give your an-swer in the answer sheets.Algorithm 1Require: Int n ≥ 1x ← 0for i = 1 ... √n dofor j = 1 ... i dox ← x + iend forend forreturn x[3 marks](b) Consider the following recurrence:T (n) = T (n − 1) + 1 , for every n ≥ 2T (1) = 1 .For each of the following statements, mark in the answer sheets whether thestatement is true or false.1. T (n) = Θ (2n)2. T (n) = Θ n2
3. T (n) = Θ (log n)4. T (n) = Θ (n)[3 marks]Page 3 of 4 Turn Over/Qu. continues . . .

Q1. This question is about Big-O notation and loop invariants.

(a) For each of the following statements, mark in the answer sheets whether the statement is true or false.

1. 5 ∈ Ω(n)
   • False. The constant 5 is not in Ω(n) because Ω(n) represents functions that grow at least as fast as n, and 5 does not grow with n.
2. log n /∈ O(n^2)
   • True. log n grows slower than n^2, so log n is indeed in O(n^2).
3. 2^n ∈ O(log n)
   • False. 2^n grows exponentially, while log n grows logarithmically. Therefore, 2^n is not in O(log n).

(b) What is the smallest integer n0 such that, for every n ≥ n0, the inequality 12n^2 ≥ 16n holds?

• To find n0, solve the inequality 12n^2 ≥ 16n: 12n^2 - 16n ≥ 0 4n(3n - 4) ≥ 0 n(3n - 4) ≥ 0 n ≥ 4/3
• The smallest integer n0 is 2.

(c) Order the following sets so that each is a subset of the one that comes after it: (1) O(log n) (2) O(log log n) (3) O(2^n) (4) O(√n)

• The correct order is: O(log log n) ⊆ O(log n) ⊆ O(√n) ⊆ O(2^n)
• Therefore, the permutation is: 2, 1, 4, 3

Q2. This question is about sorting.

(a) For each of the following statements, mark in the answer sheets whether the statement is true or false.

1. Insertionsort is a dynamic programming algorithm.
   • False. Insertionsort is a comparison-based sorting algorithm, not a dynamic programming algorithm.
2. The recursion tree of a run of Mergesort on an instance of size n has a depth of O(log n).
   • True. Mergesort divides the array in half at each level of recursion, resulting in a recursion tree depth of O(log n).

(b) For the following input to Insertionsort, state the runtime of the algorithm using Θ(.)-notation: Integer array A of length n with A[i] = n − i for every 0 ≤ i ≤ n − 1.

• The array is in reverse order, so Insertionsort will take the maximum time to sort it. The runtime is Θ(n^2).

Q3. This question concerns algorithmic design principles and recurrences.

(a) Determine the runtime of Algorithm 1 using Big “Theta” notation. Algorithm 1 Require: Int n ≥ 1 x ← 0 for i = 1 ... √n do for j = 1 ... i do x ← x + i end for end for return x

• The outer loop runs √n times, and the inner loop runs i times for each iteration of the outer loop. The total number of iterations is: ∑(i=1 to √n) i = (√n(√n + 1))/2 = Θ(n)
• Therefore, the runtime is Θ(n).

(b) Consider the following recurrence: T(n) = T(n − 1) + 1 , for every n ≥ 2 T(1) = 1 For each of the following statements, mark in the answer sheets whether the statement is true or false.

1. T(n) = Θ(2^n)
   • False. The recurrence relation does not grow exponentially.
2. T(n) = Θ(n^2)
   • False. The recurrence relation does not grow quadratically.
3. T(n) = Θ(log n)
   • False. The recurrence relation does not grow logarithmically.
4. T(n) = Θ(n)
   • True. The recurrence relation grows linearly.