2023年11月25日

Web代写 | COMP 4601A Lab #4

本次加拿大作业是算法代写相关的一个assignment

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)