algorithm - Running time of quicksort -


suppose b(n) , w(n) respectively best case , worst case asymptotic running times sorting array of size n using quick sort. consider 2 statements:

(1): b(n) o(w(n))
(2): b(n) theta(w(n))

select 1 answer:

a. both (1) , (2) true
b. (1) true (2) false
c. (1) false (2) true
d. both (1) , (2) false

i think answer not sure

b(n) = o(n * lg(n))

w(n) = o(n^2)

1) b(n) < w(n) implying b(n) = o(w(n)).

2) b(n) = theta(w(n)) equals w(n) = o(b(n)). before b(n) < w(n), therefore w(n) not bounded b(n), making 2nd statement incorrect.

solution b, first statement true , second false.


Comments

Popular posts from this blog

css - SVG using textPath a symbol not rendering in Firefox -

Java 8 + Maven Javadoc plugin: Error fetching URL -

datatable - Matlab struct computations -