(log2 n)999999999 ∈ O(n0.0000000000001)

Determine the big-O notation for the following:a. 5n5/2 + n2/5b. 6log(n) + 9nc. 3n4 + nlog(n)d. 5n2 + n3/2

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 . . .

Big O Notation

Given the precise definition of Big O notation, for a c of 9 and a T(n) = 6n2 - 19n + 3, what is the value n0 such that T(n) <= c * O( n2 ) for all n > n0?

Evaluate log10(11000)