1) Consider the assertions below. Prove or disprove the assertion using limits, possibly with L’Hoˆpital’s rule....

Question

Question

1) Consider the assertions below. Prove or disprove the assertion using limits, possibly with L’Hoˆpital’s rule....

1) Consider the assertions below. Prove or disprove the assertion using limits, possibly with L’Hoˆpital’s rule. Also, if the assertion is true, show that it is true directly from the definition of the asymptotic notation and derive values for the relevant constants.

(a) 3n^2 + 5n + 7 ∈ O(n^2)

(b) 5(n − 2)! ∈ Θ(n!)

(c) $^3\sqrt[\sqrt[]{n^3-5}{}$ ∈ Θ(n)

2) Give the recurrence relation where indicated or solve the given recurrence relation by algebraically unrolling it.

(a) Give a recurrence relation, T(n), and its initial condition for the sequence 3, 5, 9, 17, 33, 65 ··· .

(b) Solve the relation in (a).

(c) Solve T(n) = cn + T(n − 1) with the initial condition T(1) = 1.

(d) Solve T(n) = αT(n / α) + βn with the initial condition T(1) = 1.

engineering Computer-Science

Add a comment Improve this question Transcribed image text

Answer 1

Answer #1

eim 3 isa finite Hent value Here n-2 im f(n Hence

Add a comment

Answer 2

Similar Homework Help Questions

Solve the recurrence relation T(n) = 2T(n / 2) + 3n where T(1) = 1 and...

Solve the recurrence relation T(n) = 2T(n / 2) + 3n where T(1) = 1 and k n = 2 for a nonnegative integer k. Your answer should be a precise function of n in closed form. An asymptotic answer is not acceptable. Justify your solution.
1. Solve the recurrence relation T(n) = 2T(n/2) + n, T(1) = 1 and prove your...

1. Solve the recurrence relation T(n) = 2T(n/2) + n, T(1) = 1 and prove your result is correct by induction. What is the order of growth? 2. I will give you a shortcut for solving recurrence relations like the previous problem called the Master Theorem. Suppose T(n) = aT(n/b) + f(n) where f(n) = Θ(n d ) with d≥0. Then T(n) is: • Θ(n d ) if a < bd • Θ(n d lg n) if a = b...
Let f(n) = 5n^2. Prove that f(n) = O(n^3). Let f(n) = 7n^2. Prove that f(n)...

Let f(n) = 5n^2. Prove that f(n) = O(n^3). Let f(n) = 7n^2. Prove that f(n) = Ω(n). Let f(n) = 3n. Prove that f(n) =ꙍ (√n). Let f(n) = 3n+2. Prove that f(n) = Θ (n). Let k > 0 and c > 0 be any positive constants. Prove that (n + k)c = O(nc). Prove that lg(n!) = O(n lg n). Let g(n) = log10(n). Prove that g(n) = Θ(lg n). (hint: ???? ? = ???? ?)???? ?...

Solve the recurrence relation T(n)=T(n1/2)+1 and give a Θ bound. Assume that T (n) is constant for sufficiently small n....

Solve the recurrence relation T(n)=T(n1/2)+1 and give a Θ bound. Assume that T (n) is constant for sufficiently small n. Can you show a verification of the recurrence relation? I've not been able to solve the verification part so far note: n1/2 is square root(n)
2. Asymptotic Notation (8 points) Show the following using the definitions of O, Ω, and Θ....

2. Asymptotic Notation (8 points) Show the following using the definitions of O, Ω, and Θ. (1) (2 points) 2n 3 + n 2 + 4 ∈ Θ(n 3 ) (2) (2 points) 3n 4 − 9n 2 + 4n ∈ Θ(n 4 ) (Hint: careful with the negative number) (3) (4 points) Suppose f(n) ∈ O(g1(n)) and f(n) ∈ O(g2(n)). Which of the following are true? Justify your answers using the definition of O. Give a counter example if...
For each of the following recursive methods available on the class handout, derive a worst-case recurrence...

For each of the following recursive methods available on the class handout, derive a worst-case recurrence relation along with initial condition(s) and solve the relation to analyze the time complexity of the method. The time complexity must be given in a big-O notation. 1. digitSum(int n) - summing the digits of integer: int digitSum(int n) { if (n < 10) return n; return (digitSum(n/10) + n%10); } 2. void reverseA(int l, int r) - reversing array: void...

True or false? Question 6 1 pts Every prime number other than 2 can be expressed...

True or false? Question 6 1 pts Every prime number other than 2 can be expressed in the form of 4k + 1 or 4k – 3 for some k E Z. True False Question 8 1 pts Suppose that algorithm A has running time na + 10 log2 (n) and the algorithm B has the running time n log2 (n) + 5n (where both depend on the input value n). Then for a sufficiently large input value n, algorithm...
1. Give an asymptotically tight bound to each of the following expressions: 3n^2 + 2n^3 3n...

1. Give an asymptotically tight bound to each of the following expressions: 3n^2 + 2n^3 3n log n + 2n^2 2^n + 3^n 2. Arrange the following asymptotic family from lower order to higher order. The first has been done for you. O(n log n) O(n^3) O(log n) O(n^2 log n) O(n) O(3^n) O(2^n) 3. At work, Peter needs to solve a problem of different sizes. He has two algorithms available to solve the problem. Algorithm A can solve the...
7. Consider the following proposed sorting algorithm supersort (int n, int start, int end, keytype SI1)1...

7. Consider the following proposed sorting algorithm supersort (int n, int start, int end, keytype SI1)1 if(n > 1) { if (SIstart] > S[end]) swap SIstart] with Stend]; supersort(n-l, start, end-1, s) supersort (n-1, start+, end, S) a) 3 pts) Give a recurrence relation (with initial condition) that describes the complexity of this sort algorithm b) (4 pts) Solve the recurrence froma) c) (3 pts) Is supersort guaranteed to correctly sort the list of items? Justify your answer. (A formal...

In this exercise we consider finding the first five coefficients in the series solution of the first order linear initial value problem (+3)y' 2y 0 subject to the initial condition y(0) 1. Si...

In this exercise we consider finding the first five coefficients in the series solution of the first order linear initial value problem (+3)y' 2y 0 subject to the initial condition y(0) 1. Since the equation has an ordinary point at z 0 it has a power series solution in the form We learned how to easily solve problems like this separation of variables but here we want to consider the power series method (1) Insert the formal power series into...

1) Consider the assertions below. Prove or disprove the assertion using limits, possibly with L’Hoˆpital’s rule....

Homework Answers

Add Answer to:
1) Consider the assertions below. Prove or disprove the assertion using limits, possibly with L’Hoˆpital’s rule....

Post as a guest

Earn Coins

Solve the recurrence relation T(n) = 2T(n / 2) + 3n where T(1) = 1 and...

1. Solve the recurrence relation T(n) = 2T(n/2) + n, T(1) = 1 and prove your...

Let f(n) = 5n^2. Prove that f(n) = O(n^3). Let f(n) = 7n^2. Prove that f(n)...

Solve the recurrence relation T(n)=T(n1/2)+1 and give a Θ bound. Assume that T (n) is constant for sufficiently small n....

2. Asymptotic Notation (8 points) Show the following using the definitions of O, Ω, and Θ....

For each of the following recursive methods available on the class handout, derive a worst-case recurrence...

True or false? Question 6 1 pts Every prime number other than 2 can be expressed...

1. Give an asymptotically tight bound to each of the following expressions: 3n^2 + 2n^3 3n...

7. Consider the following proposed sorting algorithm supersort (int n, int start, int end, keytype SI1)1...

In this exercise we consider finding the first five coefficients in the series solution of the first order linear initial value problem (+3)y' 2y 0 subject to the initial condition y(0) 1. Si...

1) Consider the assertions below. Prove or disprove the assertion using limits, possibly with L’Hoˆpital’s rule....

Homework Answers

Add Answer to: 1) Consider the assertions below. Prove or disprove the assertion using limits, possibly with L’Hoˆpital’s rule....

Post as a guest

Earn Coins

Add Answer to:
1) Consider the assertions below. Prove or disprove the assertion using limits, possibly with L’Hoˆpital’s rule....