Math Is Fun Forum

  Discussion about math, puzzles, games and fun.   Useful symbols: ÷ × ½ √ ∞ ≠ ≤ ≥ ≈ ⇒ ± ∈ Δ θ ∴ ∑ ∫ • π ƒ -¹ ² ³ °

You are not logged in.

#1 Help Me ! » Need help understanding this proof » 2016-07-15 08:58:55

harrorm
Replies: 2

Problem: Show that f(n) = 1/2n^2 - 1/2n = theta(n^2)

theta(g(n) = { f(n) : there exist positive constants c1, c2, and n0 such that 0 <= c1g(n) <= f(n) <= c2g(n) for all n >= n0

Proof:
1. 1/2n^2 - 1/2n <= 1/2n^2 ----> for all n >= 0 c2 = 1/2 ------ for this does c2 = 1/2 because it can be any positive constant?
2. 1/2n^2 - 1/2n >= [1/2n^2 - 1/2n * 1/2n] -----> for all n >= 2 -------- everything in the bracket, I don't understand where it came from

So for #2, where did the "1/2n^2 - 1/2n * 1/2n" come from? I know it suppose to represent c1g(n), but not sure why it's 1/2n^2 - 1/2n * 1/2n and not 1/2n^2 like for c2g(n)

#2 Re: Help Me ! » Need explanation on a summation transformation » 2016-07-07 18:19:10

Hi, yeah I figured out that one. Thanks though, but maybe you can explain this one?
byRZZZU.png
How did n - 1 become n - 2 and 2^i - 1 become 2^i?

#4 Re: Help Me ! » Reccurence problem - Need clear explanation » 2016-06-30 13:46:02

Well he originally had: ((1/2)cn^3 + n)
Then he said to rewrite that as: cn^3 and minus what he didn't want, so he ended up with: cn^3 - ((1/2)cn^3 - n).

= ((1/2)cn^3 + n)
= cn^3 - ((1/2)cn^3 - n)
<= cn^3

How did he get to the final line (<= cn^3). It seems like there are steps in between that I'm not understanding?

#5 Re: Help Me ! » Reccurence problem - Need clear explanation » 2016-06-28 08:11:07

I'm not asking if the step is correct. I'm asking for an explanation as to why subtracting (1/2cn^3 - n) from 1/2cn^3 + n results in cn^3. That's what I need help understanding, like why did he subtract that instead of anything else.

#6 Re: Help Me ! » Reccurence problem - Need clear explanation » 2016-06-28 03:07:24

n is defined as sufficiently large n. So he does this in the video: cn^3 - (1/2cn^3 - n) to get the final answer as <= cn^3.

#7 Re: Help Me ! » Reccurence problem - Need clear explanation » 2016-06-28 01:55:14

Thanks for the reply! Well it's part of an online class I'm taking so no way to get around it. The part I'm confused about is that he set cn^3 to to 1/2cn^3 + n. So wouldn't subtracting 1/2cn^3 from itself be zero? Why would it be cn^3?

#8 Help Me ! » Reccurence problem - Need clear explanation » 2016-06-27 18:25:44

harrorm
Replies: 11

Hi,

I was watching the MIT video lectures and at the 25:17 mark, the instructor talks about residual. Can someone please give a clear explanation why he subtracted 1/2cn^3? I'm pretty bad at math, so I would really appreciate it if the explanations are clear as if I don't know anything! hmm

Vid lecture: https://youtu.be/whjt_N9uYFI?t=25m17s

Board footer

Powered by FluxBB