程序代写代做代考 Computer Science Department – Rutgers University Spring 2018

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