Consider an algorithm that contains loops of this form: for (i = 1 through n ) {
ID: 3685136 • Letter: C
Question
Consider an algorithm that contains loops of this form:
for (i = 1 through n )
{ for (j = 1 through i)
{ for (k = 1 through 10)
{ Task T
}
}
}
If task T requires t time units, the loop on j requires ______ time units.
a. t * i
b. 10 * t * i
c. (10 * t) + i
d. 10 * t
In the best case, a sequential search is ______.
a. O(n)
b. O(1)
c. O(log2 n)
d. O(n2)
The values of the growth-rate function O(log2 n) grow faster than the values of the growth-rate function O(n).
a. True
b. False
Function f(n) is O( g(n) ) if f(n)>g(n) for all n>0.
a. True
b. False
Explanation / Answer
1)
Therefore the correct option is b.
2)
Therefore the correct option is b.
3)
O(1) < O(log2 n) < O(n) < O(n log2 n) <O(n2) < O( n3) <…..< O(2n)
Therefore the given statement is False.
4)
Big-o definition:
Therefore the given statement is False.