Order the following functions by growth rate. Write a 1 by the fastest, a 2 by the next fastest, etc. If two functions grow at the same rate, write the same number by both of them.
Which recurrence best describes the work done by a typical binary search algorithm?
For each of the following code snippets indicate the running time using Big-Oh notation (a reasonable upper bound is good enough - no need for an asymptotically tight bound).
sum = 0; if ( condition == true ) for ( i = 0 ; i < n ; ++i ) ++sum; else for ( i = n ; i > sum * 2 ; --i ) ++sum;
sum = 0; for ( i = 0 ; i < n ; ++i ) for ( j = 0 ; j < n ; ++j ) ++sum;
sum = 0; for ( i = 0 ; i < n ; ++i ) for ( j = n * n ; j > 0 ; --j ) ++sum;
sum = 0; for ( i = 0 ; i < n ; ++i ) for ( j = 0 ; j < i ; ++j ) ++sum;
sum = 0; for ( i = 0 ; i < n ; ++i ) for ( j = 0 ; j < i * i ; ++j ) for ( k = 0 ; k < j ; ++k ) ++sum;
sum = 0; for ( i = 0 ; i < n ; ++i ) for ( j = 0 ; j < i * i ; ++j ) if ( j % i == 0 ) for ( k = 0 ; k < j ; ++k ) ++sum;
Suppose T1(N) = O(f(N)) and T2(N) = O(f(N)), which of the following are true?
What is the Big-Oh asymptotic bound for each of the following recurrences?
The sum of xi as i goes from 0 to infinity is equal to 1 / ( 1 - x ) if and only if:
Which of the following is not equal to a3 + 4ab2?
Which of the following has the greatest value?
Which of the choices below is a tight asymptotic bound for a function whose runtime is described by the following recurrence?
T(n) = T( n - 1 ) + n
T(1) = 1
What is the flaw in the following inductive proof?
Theorem: All dogs are the same color.
Proof: Proof by induction. Formally, we wish to prove that, for any set of n dogs, all dogs are the same color.
Base case: n = 1: Clearly, if we have a set of only one dog, the dog is the same color as itself.
Induction step: We assume that the property is true for some n, and show that it is true for n + 1. We select two sets of n dogs A and B such that all of the n + 1 dogs occur in at least one of the sets A or B, and there is one dog that appears in both sets (call this dog ``Rover''). Since A and B are of size n, we know from the Induction Hypothesis that the dogs in each set are the same color. Moreover, since Rover is in both sets, both sets must be the same color. So, the property holds for n + 1 dogs. QED.
I once heard a story similar to the following: A wise man in ancient China had done a great service to the ruler. The ruler wanted to express his gratitude and offered the wise man the following options
For the purposes of this question, assume a pound of rice has 10,000 grains, and a ton has 2,000 pounds.
Which option would you choose? Why?
How many grains of rice would be on square N of the chess board?
Imagine that the chess board is infinite, what square would have G grains of rice on it? Use Big-Oh notation if you feel better about doing so.