Prefix sums of a sequence of numbers are given by a second sequence of numbers defined as
The Python code below computes prefix sums.
1 2 3 4 5 6 7 8 9 |
|
Analyze the the code and find the line or lines that will be executed the greatest number of times.
The fragment of Java code below describes a recursive method that takes two integer parameters and and returns an integer.
1 2 3 4 5 6 7 8 9 10 11 12 13 |
|
Analysis shows us that the running time of this function for large can be expressed as for some function . What is a valid function ?
Details and assumptions
int
primitive type and assume the behavior of the method is not affected for large inputs.1 2 3 4 5 6 7 8 9 10 11 |
|
Consider the recursive algorithm above, where the random(int n)
spends one unit of time to return a random integer which is evenly distributed within the range . If the average processing time is , what is the value of ?
Assume that all instructions other than the random cost a negligible amount of time.
The simple recursive python program below can be used to compute the Fibonnaci number.
1 2 3 4 5 |
|
It can be shown that a tight bound of this program is given by for some function . What family of functions is in?
Details and assumptions
An obvious algorithm for exponentiation () takes multiplications. Suppose we propose a faster algorithm for the case where . The "Big-O" complexity of such an algorithm can be expressed as:
Take the value of for an arbitrary . If we multiply by some constant , how will the value of most likely change?