Quantitative Methods Answers

T(n) = 2T([sqrt(n)])+1
T(1) = 1
Which of the following is true?

A) T(n) = Theta (log log n)
B) T(n) = Theta (log n)
C) T(n) = Theta (sqrt(n))
D) T(n) = Theta (n)

The median of n elements can be found in O(n) time. Which one of the following
is correct about the complexity of quick sort, in which median is selected as
pivot?
(A) Theta(n)
(B) Theta (n log n)
(C) Theta(n^ 2 )
(D) Theta( n^3 )

suppose there are (ceiling[log n]) sorted lists of (floor[n/log n]) elements each.
Time complexity of producing a sorted list of all these element (use heap data structure)
a]O(n log log n)
b]theta(n log n)
c]Big Omega(n log n)
d]Big Omega(n^1.5)

A chartered accountant applies for a job in two firms X and Y. He estimates that the probability of his being selected in firm X is 0.7 and being rejected in Y is 0.5 and the probability that atleast one of his applications rejected is 0.6. What is the probability that he will be selected in one of the firms?

Consider the following (unrealistic!) investment problem.We have a set S of n potential investments, each given by a pair of floating point numbers (amount, estimated return) There is a total amount A to invest; we want to select investments to maximise the return on this amount.One may select each investment (a,r) as a whole (spending all of a, and getting r return) or only can select only a fraction f (spending (f*a), and getting (f*r) return). The estimated return of a set of selections is the sum of the returns of the individual selections. Obviously, in selecting elements of S, we cannot spend more than the total amount A available.Describe an efficient algorithm for computing the maximum estimated return that can be realised with amount A and set of investments S. What is the time complexity of your algorithm (in big-oh notation)? Is it the best possible? It is fine to describe your algorithm in words and/or pseudocode; there's no need to include code in a programming language.