Java Reference
In-Depth Information
(f) sum=0;
for(i=1;i<=n;i * =2)
for(j=1;j<=n;j++)
sum++;
(g) Assume that array A contains n values, Random takes constant time,
and sort takes n log n steps.
for(i=0;i<n;i++){
for(j=0;j<n;j++)
A[i]=DSutil.random(n);
sort(A);
}
(h) Assume array A contains a random permutation of the values from 0 to
n 1.
sum=0;
for(i=0;i<n;i++)
for(j=0;A[j]!=i;j++)
sum++;
(i) sum=0;
if(EVEN(n))
for(i=0;i<n;i++)
sum++;
else
sum=sum+n;
3.13 Show that big-Theta notation () defines an equivalence relation on the set
of functions.
3.14 Give the best lower bound that you can for the following code fragment, as a
function of the initial value of n.
while(n>1)
if(ODD(n))
n=3 * n+1;
else
n=n/2;
Do you think that the upper bound is likely to be the same as the answer you
gave for the lower bound?
3.15 Does every algorithm have a running-time equation? In other words, are
the upper and lower bounds for the running time (on any specified class of
inputs) always the same?
3.16 Does every problem for which there exists some algorithm have a running-
time equation? In other words, for every problem, and for any specified
class of inputs, is there some algorithm whose upper bound is equal to the
problem's lower bound?
3.17 Given an array storing integers ordered by value, modify the binary search
routine to return the position of the first integer with value K in the situation
where K can appear multiple times in the array. Be sure that your algorithm
Search WWH ::




Custom Search