Question

6) This question is part of Exercise 3-4 on page 62 of CLRS, but the letters arent all the same. Answer TRUE or FALSE for each of the following statements. TRUE means that the statement is TRUE for any asymptotically positive functions f(n) and g(n). Otherwise, answer FALSE. You dont have to Prove or Disprove these statements... but you should learn how to do that. f(n)- O( g(n)) implies g(n) O( f(n)) b) This is part a in Exercise 3-4. This is part b in Exercise 3-4. This is part g in Exercise 3-4. This is part h in Exercise 3-4. a) fin) + g(n)-Θ( min(f(n), g(n)) ) f(n) = Θ( f(n/2) ) c) d) fin) + 0( f(n) )= Θ( f(n) ) Part d of Question 6 warrants some explanation. What it asks is whether f(n) plus any function that is o(Nn)) must always be Θ( f(n) ), for any asymptotically positive function f(n).7) Prove that for anyb> 1, n = (o( bn ) The Handout CommonFunctions.pdf, which is posted on Piazza under Resources-> General Resources, provides you with an approximation of n! using Stirlings formula that you can use to prove this. That Handout also gives you some information about floor, ceiling and logarithms, that weve already discussed in class. It mentions this problem, but it doesnt prove it.

0 0
Add a comment Improve this question Transcribed image text
Answer #1

As per Chegg answering guidelines, I'm answering only the first 4 sub-parts:-

6)

a) FALSE

Take f(n) = 1 and g(n) = n .

Here f(n) = O(g(n)) but g(n) is not O(f(n)).

b) FALSE

As, f(n) + g(n) = θ(max(f(n) g(n)))

c) FALSE

Let f(n) = 22n then f(n/2) = 2n and 22n is not O(2n).

d) TRUE

Add a comment
Know the answer?
Add Answer to:
6) This question is part of Exercise 3-4 on page 62 of CLRS, but the letters...
Your Answer:

Post as a guest

Your Name:

What's your source?

Earn Coins

Coins can be redeemed for fabulous gifts.

Not the answer you're looking for? Ask your own homework help question. Our experts will answer your question WITHIN MINUTES for Free.
Similar Homework Help Questions
  • Since this is my last chance to post question, I have to post all of them....

    Since this is my last chance to post question, I have to post all of them. I will be very appreciate if you can answer all the parts!!   Thumbs up guaranteed 1. (30 pts) Consider the following functions fb(n)31+1 +5n4 fa(n) 216 f(n) ((9n2) (6n) (121))1/2 fi(n)n-1 For these functions, do the following: (a) Prove the asymptotic complexity of each of the functions, in sim- plest terms. That is, for each function f, find the "simplest" function g such that...

  • Multivariable Calculus help with the magnitude of angular momentum: My questions is exercise 4 but I have attached exercise 1 and other notes that I was provided 4 Exercise 4. In any mechanics proble...

    Multivariable Calculus help with the magnitude of angular momentum: My questions is exercise 4 but I have attached exercise 1 and other notes that I was provided 4 Exercise 4. In any mechanics problem where the mass m is constant, the position vector F sweeps out equal areas in equal times the magnitude of the angular momentum ILI is conserved (Note: be sure to prove "if and only if") (Note: don't try to use Exercise 2 in the proof of...

  • Question 1 [22 marks] (Chapt ers 2, 3, 4, 5, and 6) Let A e Rn...

    Question 1 [22 marks] (Chapt ers 2, 3, 4, 5, and 6) Let A e Rn be an (n x n) matrix and be R. Consider the problem 1 (P2) min2+ s.t. xe R" 1Ax-bil2 1 where & > O is fixed and Il IIl denot es the 2-norm. Call g.(x)=l|2 the objective function of problem (P2) 1Ax-bl2 i) [3 marks] Compute the gradient of g, and use it to show that the solution xi of this problem verifies (I+EATA)(x)...

  • hi this is my first question multiple choose its only 4 question in the firsr part...

    hi this is my first question multiple choose its only 4 question in the firsr part Question 1 Not yet answered Marked out of 50.00 P Flag question A box with mass m = 2 kg slides up an inclined ramp with length d = 5 m as shown in the Figure. The box starts with an initial speed v; at the bottom of the ramp. The box slows down as it slides up due to a constant friction force...

  • Chapter 12 Patlent Teaching 105 Part 3. Review Questions Circle the correct answer(s). In some questions,...

    Chapter 12 Patlent Teaching 105 Part 3. Review Questions Circle the correct answer(s). In some questions, more than one answer is correct. Select all that apply 13. Which of the following is the best rationale for nurses 19. Tell the patient to wait until you harve fin ished teaching before asking questions. Adults learn best when they understand the relevance of the information presented Do not assume an interpreter will be needed. Always ask the patient if he or she...

  • Lab 6 Instructions Objectives: • Executing and experimenting with programs that handle array related topics such...

    Lab 6 Instructions Objectives: • Executing and experimenting with programs that handle array related topics such as declaration, initialization, storing, retrieving, and processing elements. • Effectively manipulating and using ArrayList objects. • Becoming familiar with the use of arrays as method arguments and how array elements are passed to and returned from the called method. • Mastering the use of various debugging tools available on the Eclipse IDU. Important: EVERY one of the following Activities MUST be in a separate...

ADVERTISEMENT
Free Homework Help App
Download From Google Play
Scan Your Homework
to Get Instant Free Answers
Need Online Homework Help?
Ask a Question
Get Answers For Free
Most questions answered within 3 hours.
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT