Computer Science Department – Rutgers University Spring 2018
CS 205: Final Exam Question 2 – Big O 16:198:205
1) Formally prove that if f = O(h) and g = O(h) then f + g = O(h).
2) True or false – give a mathematical justification:
a) n = O(n2).
b) n(n + 1)(n + 2) − n3 = O(n3).
c) n(n + 1)(n + 2) − n3 = O(n2).
d) n lnn = O(n2).
e) n2 = O(n lnn).
f) 1/n = O(1).
g) 1000000n = O(n).
h) 2n = O(3n).
i) 3n = O(2n).
j)
∑n
i=1 i(i + 1)(i + 2) = O(n
4).
Recall the idea of mergesort: to sort a list, divide a list in two, sort the two halves, and merge them to form a
sorted whole. In class, we gave an argument that the complexity of mergesort on a list of N elements could therefore
be described as
M(N) = M(N/2) sort the left half + M(N/2) sort the right half + N merge the two halves = 2M(N/2) + N. (1)
Noting that M(1) = 1, since sorting a list of size 1 is easy, this led to an overall complexity of M(N) = O(N lnN).
Your good buddy suggests the following: If mergesort gets such good performance dividing the list into two halves
and merging them, imagine how fast a mergesort would be that split the list to sort into three parts, sorted them,
then merged the result.
3) Like the recursive relation above, give a rough description of the overall worst case complexity of this tri-
mergesort.
4) In terms of big-O, which approach has the smaller complexity?
5) In your opinion, is it worth the additional effort and overhead it would take to implement this approach?
Justify.
1