Can somebody please help me with these problems? These are from the textbook Fou
ID: 670782 • Letter: C
Question
Can somebody please help me with these problems? These are from the textbook Foundations of Algorithms by Richard Neapolitan and Kumarss Naimipour.
17. Using the Properties of Order show that 5n^5+4n^4+6n^3+2n^2+n+7 theta (n^5).
27. Show the correctness of the following statements.
a. lg n O(n)
b. n O(n lg n)
c. n lg n O(n2)
d. 2^n 5ln n
e. lg^3 n (n^0.5)
34. What is the time complexity T(n) of the nested loops below? For simplicity, you may assume that n is a power of 2. That is, n = 2k for some positive integer k.
i = n;
while (i >=1){
j=i;
while (j<=n){
<body of the while loop> //Needs theta(1),
j=2*j;
}
i=[i/2];
}
37. Give a (lg n) algorithm that computes the remainder when xn is divided by p. For simplicity, you may assume that n is a power of 2. That is, n = 2k for some positive integer k.
Thank you!
Explanation / Answer
17.Using the Properties of Order show that 5n^5+4n^4+6n^3+2n^2+n+7 theta (n^5).
sol-
5n^5+4n^4+6n^3+2n^2+n+7 theta (n^5).
according the property of order 6 and 7
i.e g(n)o(f(n)) and c8g(n)+d*h(n)(f(n)) and 5n^5 theta (n^5).
which mean 5n^5+4n^4 theta (n^5).
which mean 5n^5+4n^4+6n^3 theta (n^5).
which means 5n^5+4n^4+6n^3+2n^2 theta (n^5).
again 5n^5+4n^4+6n^3+2n^2+n+7 theta (n^5).
Practically we do not repeatedly apeal the property but we can simply relize that we can throw out the low order term.
34.
The while loop which is the outeer loop divide n by 2 with each iteration until it is less than 1,hence we get log2(n) time.for time complexity we have to go through the inner loop which is iterate for the value of i(for each outter loop).
i:n = 1 iteration
i:n/2 = 2 iterations
i:n/4 = 3 iterations
here so on..
Hence the time complexity of 1 + 2 +... + log2(n), which equals to T(n)=(lgn+1) +n^2.
37. Give a (lg n) algorithm that computes the remainder when xn is divided by p.
here
27
a) lg n O(n)
here we know that lim(n) n/ log n = lim(n) 1/(1/(n ln 10)) = .
Hence, we follow log n < n for sufficiently large n.
Here the inequality is actually true for all positive integers n, because
f(n) = n - log n > 0 for all n in N.
f(1) = 1 - 0 > 0 and f '(n) = 1 - 1/(n ln 10) > 0 ( n > 1/ln 10),
thus f is increasing for all positive integers n is also increasing.
hence, log n = O(n).
c) n lg n O(n2)
here, f(n)=nlogn f(n)=nlogn then f(n)f(n) is a member of O(nlogn)O(nlogn).so we take a large value kk thus ikik and f(i)c1ilog(i)f(i)c1ilog(i).
we know that f(n)f(n) is a member of O(nlogn)O(nlogn) then f(n)f(n) is a member of O(n2)O(n2),so we can tak large value of kk and showing that ikik and f(i)c2ilogif(i)c2ilogi which turns out to be f(i)=i2logif(i)=i2logi which is a member of O(n2)O(n2).