English 字幕

← Big-Theta Reflexive - Intro to Algorithms


Showing Revision 2 created 05/25/2016 by Udacity Robot.

  1. If you're a little bit test-wise, you should be able to guess this even if you don't understand why.
  2. The answer is this, but let me explain why.
  3. What we'd like to show is that if we're given a function f(n) that is in Θ(g(n))
  4. that we can turn that around and also infer that that means g(n) is in Θ(f(n)).
  5. The way we're going to show this is to go back to the definition of Big Theta.
  6. Here's the definition--that there is some constant c₁ and c₂ bigger than 0
  7. and a a threshold n₀ such that f(n) lies between c₁ of g(n) and c₂ of g(n) for all n
  8. bigger than the threshold n₀.
  9. We can infer from this that by dividing through this equation dividing through by c₁,
  10. which is a positive number, we get a new set of inequalities--like so--
  11. where g(n) is now sandwiched between 1/c₁ of f(n) and 0.
  12. We can do that same trick again dividing through this equation by c₂.
  13. We see that 1/c₂ of f(n) is less than or equal to g(n).
  14. We can combine these two facts to show that g(n) is sandwiched between
  15. 1/c₂ of f(n) and 1/c₁ of f(n)--like so.
  16. Notice that this1/c₂ and 1/c₁--those are just constants.
  17. It equivalent to say that this 1/c₂ is just a constant, and we can rename it c₁,
  18. and this one 1/c₁ is just a constant and we can rename it c₂,
  19. and this is exactly the definition of Big Theta,
  20. so we can infer from this that g(n) is in Θ(f(n)).