Computer Science Department – Rutgers University
Spring 2018
CS 205: Final Exam Question 2 – Big O
1) Formallyprovethatiff=O(h)andg=O(h)thenf+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) nlnn = O(n2).
e) n2 = O(nlnn). f) 1/n = O(1).
g) 1000000n = O(n). h) 2n = O(3n).
i) 3n = O(2n).
j) ni=1 i(i + 1)(i + 2) = O(n4).
16:198:205
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