366 views
2 votes
2 votes

Order the following functions by growth rate :

  1. $\log n$
  2. $n/\log n$
  3. $(3/2)^n$
  4. $n\log^2 n$
    1. a. $\log n$ $\quad$ b. $n/\log n$  $\quad$ d. $n\log^2 n$  $\quad$ c. $(3/2)^n$ 
    2. d. $n\log^2 n$ $\quad$ c. (3/2)$^n$  $\quad$ a. $\log n$$\quad$ b. $n/log n$
    3. a. $\log n$ $\quad$ d.$n\log^2 n$ $\quad$ b. $n/\log n$  $\quad$ c. (3/2)$^n$
    4. a. $\log n$ $\quad$ c. (3/2)$^n$  $\quad$ b. $n/\log n$ $\quad$ d. $n\log^2 n$

1 Answer

2 votes
2 votes
c is exponential so it has higher growth and a is logn which has least growth...b/w b and c

n/logn<= c* nlog2n

because nlog2n , we can write as  n * lognlogn

                            which is obviously larger than n/logn

for ex: let n=2^20

n*lognlogn = 2^20 *20 *20

and n/logn = 2^20/20

hence (A) is the answer
edited by
Answer:

Related questions

3 votes
3 votes
1 answer
2
Bikram asked Oct 4, 2016
499 views
Let we have 3 steps of an arbitrary program fragment whose running times are $O(n^2), \: O(n^3)$ and $O(n\log n)$, then the running time of whole program is$O(n^3)$$\Omeg...
2 votes
2 votes
2 answers
4
Bikram asked Oct 4, 2016
345 views
$$T(n) = \begin{cases} 4 & \quad if \: \: n =1 \\ T(n-1) + 4 & \quad otherwise \end{cases}$$Value of $T(1000)$ is ___