Zookal Homework Help

Homework Help

  1. Engineering
  2. Computer Science
  3. 6 this question is part of exercise 34 on page...

Question: 6 this question is part of exercise 34 on page...

Question details

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.

Solution by an expert tutor
Blurred Solution
This question has been solved
Subscribe to see this solution