Asymptotic Notation

Instructions:
Below you will find the questions which make up your homework. They are to be written out (or typed!)
and handed in online via Gradescope before the deadline.
Question 1: Asymptotic Notation
.
(a) 8 points Rank the following functions in order (non-decresasing) of their asymptotic growth. Next
to each function, write its big-Theta value, (ie. write the correct Θ(g(n)) next to each function but you
are not required to prove the big-Theta value).
log(n
3+1),
p
Assignment 1
Due date: 11:55pm on Feb. 13th .
n3
(log n) + n6
, (210+6)(2n+n),
n
2 + 1
n + log n
, 2
3n+1
,
p
n log n + 1, 4
n/2+1
, (2n+3n
)(3n+4n
),
(log 2n
)
n
, n · 2
log n
, (log(n/2))2
(b) 8 points Determine if each of the following statements are true or false. If the statement is false,
provide a counter example. If the statement is true, justify the statement using the formal definitions from
class.
1. If f(n) is O(n log n), does this imply that f(n) is also Ω(n)?
2. If f(n) is O(n
4
), does this imply that f(n) is also O(2n
)?
(c) 16 points For each of the following f(n), show that f(n) is Θ(g(n)) for the correct function g(n).
Prove your result using the definitions from class, justifying your statement is true for all n ≥ k. (provide
the value of k).
ˆ f(n) = √
n log n +
√
n
log n −
√
n
ˆ f(n) = 3n
4+n
2n−log n + 1
ˆ f(n) = 2n
· n + 100 · 4
n + n
5
log n − n
6
ˆ f(n) = n
4+1
n3−n − log n + 1000
(d) 4 points Give an example of a function f(n) that is: O(n
5
) and O(n
3
log n) and Ω((log n)
2
) and
Ω(√
n). The example must not be O(n) and must not be Ω(n
2
).
You must prove that f(n) is either O(n
5
) or O(n
3
log n).
You must also prove that f(n) is either Ω((log n)
2
) or Ω(√
n)
1
(e) 8 points Below is the link to the description of a comparison-based sorting algorithm
.
Your job:
ˆ Show the steps of the algorithm when executed on the array [10, 5, 3, 6, 1, 4, 2, 8, 7, 9].
ˆ What is the worst-case number of comparisons on array A of length n? You must describe the input
that causes this worst-case scenario, and justify the worst-case number of comparisons.
ˆ What is the best-case number of comparisons made on array A of length n? You must describe the
input that causes this best-case scenario, and justify the best-case number of comparisons.
Question 2: Recurrences
(a) 12 points Consider the the pseudo-code below for the recursive algorithm TestRec(A, s, f), which
takes as input an array A, indexed between s and f.
TestRec(A, s, f)
if s + 2 < f q1 = ⌊ 2s+f 3 ⌋ q2 = ⌊ s+2f 3 ⌋ TestRec(A, s, q2) TestRec(A, q1 + 1, f) Merge(A, s, q1, q2) #Merge sorted array from s to q1 with sorted array q1 + 1 to q2 else InsertionSort(A, s, f) ˆ Execute the algorithm on input [3, 2, 6, 7, 5, 3, 9, 10] ˆ Does this algorithm correctly sort the input array A? Justify your answer. ˆ Write the recurrence for the runtime T(n) of TestRec when run on an array of size n. ˆ Determine the runtime of the algorithm using Master Method. ˆ Determine the runtime of the algorithm using the Recursion Tree method. You may use the fact that 4 3 log 3 2 n = n log 3 2 4 3 (b) 6 points Consider the the pseudo-code below for the recursive algorithm FunnyRun(A, s, f), which takes as input an array A, indexed between s and f. FunnyRun(A,s,f) if 3 < f − s q1 = ⌊(2s + f)/3⌋ q2 = ⌊(s + 2f)/3⌋ FunnyRun(A, q1 + 1, f) FunnyRun(A, s, q2) InsertionSort(A, s, q1) FunnyRun(A, q2 + 1, f) else InsertionSort(A, s, f) Your job: Write and justify the runtime recurrence for the above algorithm. Use Master Method to find a tight upper bound for the runtime of the algorithm. (c) 4 points Update the pseudo-code for binary search from class as follows: BSearch( A, s, f, k) returns NIL if element k is not in array A, otherwise it returns the index of the element k in array A. 2 (d) 8 points Below is the pseudo-code for an algorithm that takes as input an array of positive integers, A, indexed between s and f. The algorithm prints out certain elements of the array. SillyPrint(A,s,f) if 1 < f − s q1 = ⌊(3s + f)/4⌋ q2 = ⌊(s + 3f)/4⌋ print A[q1] SillyPrint(A,q1,f) print A[q2] else print A[s] ˆ Execute the algorithm on the input [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]. ˆ Find and justify the runtime recurrence for the algorithm: T(n). ˆ Use the above recurrence to show that T(n) is O(log n) using substitution method. (e) 12 points Use the recursion tree to find a tight asymptotic bound for each of : ˆ T(n) = 2T(n/4) + n 2 ˆ T(n) = 4T(n/4) + n ˆ T(n) = 3T(n/4) + 1 ˆ T(n) = 9T(n/3) + n 2 (f) 8 points Apply the master theorem to to each of the following, or state that it does not apply: ˆ T(n) = 6T(n/2) + n 2 + n ˆ T(n) = 16T(n/4) + n 2 log n ˆ T(n) = 16T(n/4) + n 2 + log n. ˆ T(n) = 15T(n/4) + n 2 log n 3