Prefix sums of a sequence of numbers $a_0,a_1,a_2,a_3\ldots$ are given by a second sequence of numbers $s_0,s_1,s_2,s_3\ldots$ defined as
$s_j = \sum_{i=1}^{j}a_i$
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 $P$ that takes two integer parameters $x$ and $n$ 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 $n$ can be expressed as $T(n) = O(g(n))$ for some function $g(n)$. What is a valid function $g(n)$?
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 $[0,n]$. If the average processing time is $T(n)$, what is the value of $T(6)$?
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 $n^{th}$ Fibonnaci number.
1 2 3 4 5 

It can be shown that a tight bound of this program is given by $T(n) = \Theta(g(n))$ for some function $g(n)$. What is the value of $g(17)$?
Details and assumptions
An obvious algorithm for exponentiation ($x^{n}$) takes $n1$ multiplications. Suppose we propose a faster algorithm for the case where $n=2^{m}$. The "BigO" complexity of such an algorithm can be expressed as:
$T(n)=O(g(n))$
Take the value of $g(n)$ for an arbitrary $n$. If we multiply $n$ by some constant $k$, how will the value of $g(n)$ most likely change?
Problem Loading...
Note Loading...
Set Loading...