Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

COMP 4601A Lab #4

1. (7) What is the Big Oh function for each of the following functions of n. It should be as tight and as simple
as possible. For example, if t(n) = 3.5n log3n5 + log log n + 100√n, the answer should be n log3n.

All log functions are base 2. And if you use log functions in your answers, they should be base 2 as well.
There is no need to justify your answers.

2. (13) Indicate, for each pair of expressions (A,B) in the table below, whether A is O, o, Ω, or Θ of B. See
example answers for A = 2n and B = 2n+1. Assume that k > 1 and c > 1 are constants. Your answer should
be in the form of the table with ”yes” or ”no” written in each box. Also, please list all the functions in Column
A from the lowest to the highest asymptotically.

3. (15) Consider the following recursive algorithm C(i, j, x) that checks whether the array segment A[i..j] contains
key x, where i ≤ j. It return YES if x is found and NO otherwise (note that floor(x) is the floor function that
returns the largest integer that is less than or equal to x):

else
return NO
else
if C(i, floor((i+j)/2), x) = YES
return YES
else
return C(floor((i+j)/2) + 1, j, x)
if i=j then
if A[i] = x
return YES

Let t(n) be the worst case time for C(1, n, x) and assume that n is a power of 2. (a) Give a recurrence for
t(n). Don’t forget the initial condition; and (b) solve t(n) using the following methods: iteration, recursion
tree, and the masters method. No credit will be given if your recurrence is incorrect.C(i, j, x)