1. Circle one of True or False in the following questions. log(n) = O (n) True o
ID: 3821407 • Letter: 1
Question
1. Circle one of True or False in the following questions.
log(n) = O (n) True or False
f(n) + g(n) = O (max (f(n)) ; g(n)) True or False
n = o (n log(n)) True or False
2n = W (7 log(n)) True or False
?n = O (n) True or False
2. Consider the following algorithm. Assume n is a power of 2.
i ? n
while i >= 1 do
j ? i
while j <= n do
?(1) statements
j ? 2 * j
endwhile
endwhile
What is the complexity of the algorithm? Circle one of the following answers:
(i) n (ii) n log n (iii) (log n)2 (iv) n (log n)2 (v) none mentioned before
i/2Explanation / Answer
1)
a) log(n) = O(n) True
b) f(n) + g(n) = O(max(f(n);g(n))) True
c) n = o(nlogn) False
d) 2n = W(7logn(n)) --> W does not specify any time complexity.
e) n = O(n) True
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.