1. log2 n is: (A) (log10 n) (B) (log10 n) 2. log2 n is equal to: (A) log2 n log2
ID: 3573272 • Letter: 1
Question
1. log2 n is:
(A) (log10 n) (B) (log10 n)
2. log2 n is equal to: (A) log2 n
log2 10 (B) log2 n
log10 2
3. log(nm) is equal to:
(A) mlogn
(B) logn + logm
4. log(nm) is equal to: (A) nlogm
(B) logn + logm
5. log2 2 can be simpli ed to:
(A) 1
(B) log2 2 cannot be simpli ed any further
6. 2log2 n is equal to: (A) log2 n
(B) n
7. n2 is o(n3). Therefore, logn2 is ?(logn3). Choose the tightest bound.
(C) o(log10 n)
(C) log10 n log2 10
(D) log10 n log10 2
(C) (log n)m (D) nlogm
(C) mlogn (D) (log n)m
(C) 2 (D) 4
(D) little omega (E) little omicron
(C) log nlog n (D) n
(C) nlogn (D) n
(D) n (E) 2n
(A) theta
(B) big omega (C) big omicron
8. log nn is (?). (A) log n
(B) n log n 9. log 2n is (?).
(A) 2n (B) logn
10. The number of permutations of a list of n items is:
(A) n!
(B) nlogn (C) logn
(C) 2n (D) n2
Concept: relative growth rates
11. Which of the following has the correct order in terms of growth rate?
(A) 1<n<logn<n<nlogn<n2 <n3 <2n < (D) n!<nn
(B) 1<logn<n<n<nlogn<n2 <n3 <2n < (E) n!<nn
(C) 1<n<logn<n<nlogn<n2 <n3 <n!< 2n < nn
1<logn<n<n<nlogn<n2 <n3 <2n < nn<n!
1<n<logn<n<nlogn<n2 <n3 <n!< 2n<nn
12. What is the correct ordering of growth rates for the following functions:
• f(n) = n0.9 logn • g(n) = 1.1n
• h(n) = 9.9n
(A) f<g<h (B) g<f<h (C) f<h<g
(D) h<g<f (E) g<h<f (F) h<f<g
13. What is the correct ordering of growth rates for the following functions:
• f(n)=n(logn)2
• g(n) = nlog2n
• h(n)=nlog(logn)
(A) h>f>g (B) g>f>h (C) h>g>f
Concept: order notation
14. What does big Omicron roughly mean?
(A) worse than or the same as (B) better than or the same as (C) better than
15. What does roughly mean?
(A) worse than or the same as (B) the same as
(C) worse than
16. What does roughly mean?
(A) better than or the same as (B) worse than
(C) the same as
17. T or F: All algorithms are (1).
18. T or F: All algorithms are (1).
19. T or F: All algorithms are (1).
20. T or F: There exist algorithms that are (1). 21. T or F: There exist algorithms that are O(1).
(D) f>h>g (E) f>g>h (F) g>h>f
(D) the same as (E) worse than
(D) better than or the same as (E) better than
(D) better than
(E) worse than or the same as
2
22. T or F: All algorithms are O(nn).
23. Consider sorting 1,000,000 numbers with mergesort. What is the time complexity of this operation? [THINK!]
(A) constant, because n is xed (C) n log n, because mergesort takes n log n time (B) n2, because mergesort takes quadratic time
Explanation / Answer
log2 n is equal to: (B) log2 n log10 2
log(nm) is equal to (B) logn + logm
log(nm) is equal to (B) logn + logm
log2 2 can be simpli ed to: (A) 1
2log2 n is equal to: (A) log2 n
Not clear
log nn is (?). (A) log n
The number of permutations of a list of n items is: (A) n!
1<logn<n<n<nlogn<n2 <n3 <2n < nn<n!
g<f<h
g>f>h
worse than or the same as
the same as
better than or the same as
F
F
T
T
T
F
n log n, because mergesort takes n log n time
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.