# 算法代写 | Assignment 1 COSC 3P03 Algorithms

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. 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 ﬂoor 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) E-mail: itcsdx@outlook.com  微信:itcsdx 