Results 1 to 9 of 9
Like Tree3Thanks
  • 1 Post By johng
  • 1 Post By emakarov
  • 1 Post By Prove It

Math Help - Finding Theta Question (upperbound)

  1. #1
    Newbie
    Joined
    Apr 2013
    From
    Australia
    Posts
    6

    Finding Theta Question (upperbound)

    Okay so I understand how to find the upperbound and lowerbound and hence theta for some simple functions like 4n + 5nlgn + 6 but what I don't understand is how to do it for the following function

    1 + 2 + ... + n

    I understand to find the upperbound you do the following steps

    1 + 2 + ... + n ≤ n + n + ... + n x n = n^2 for all n ≥ 1

    I understand why we substitute n but where does the n x n come from? (I got this example out of my text book)

    I want to know this so I can solve

    n + 2n + 3n + ... + n^2

    I believe I would do something like this

    n + 2n + 3n + ... + n^2
    ≤ n^2 + n^2 + n^2 + ... + n^2 x n^2 = n^4 for all n ≥ 1?
    Or is it
    n + 2n + 3n + ... + n^2 ≤ n^2 + 2n^2 + 3n^2 + ... + n^2 x n^2 = ??? for all n ≥ 1?


    Also, is the upperbound n^4 or am I not on the right track at all?

    Basically I'm just trying to figure out how to find the upperbound at the moment and then I will attempt to find the lowerbound. I've been puzzling over this for a while and would really appreciate it anyone could help.

    Thanks.
    Last edited by Herblore; May 25th 2013 at 04:44 AM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    Joined
    Dec 2012
    From
    Athens, OH, USA
    Posts
    708
    Thanks
    291

    Re: Finding Theta Question (upperbound)

    Hi,
    For your first question:
    1+2+...+n\leq n+n+...+n=n^2; there are n terms in n+n+...+n.
    I think there must be a typo, there should be an = before the n\times n

    So your second problem:
    n+2n+3n+...n^2\leq n^2+n^2+...+n^2=n^2\times n=n^3; again there are n terms in n^2+n^2+...+n^2

    When I used to teach discrete math, rarely did a text book note the following easy facts. I think they really simplify big theta questions.

    Finding Theta Question (upperbound)-mhftheta.png
    Last edited by johng; May 25th 2013 at 09:11 AM.
    Thanks from Herblore
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Apr 2013
    From
    Australia
    Posts
    6

    Re: Finding Theta Question (upperbound)

    Okay thanks heaps, I think I understand. So the answer would be

    n + 2n + 3n + ... + n^2 n^2 + n^2+ ... + n^2 = n^2 x n = n^3
    n + 2n + 3n + ... + n^2 n^3
    → O(n^3)

    n + 2n + 3n + ... + n^2 ≥ [n/2]^2 + ... + (n - 1)^2 + n^2
    n + 2n + 3n + ... + n^2 ≥ [n/2]^2 + ... + [n/2]^2 + [n/2]^2
    n + 2n + 3n + ... + n^2 = [(n+1)/2][n/2]^2 ≥ (n/2)(n/2)^2 = n^3/2^3 for all n ≥ 1
    Ω(n^3(

    Ө(n^3)


    Is this correct?






    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,561
    Thanks
    785

    Re: Finding Theta Question (upperbound)

    Quote Originally Posted by Herblore View Post
    n + 2n + 3n + ... + n^2 n^2 + n^2+ ... + n^2 = n^2 x n = n^3
    n + 2n + 3n + ... + n^2 n^3
    → O(n^3)
    This is correct.

    Quote Originally Posted by Herblore View Post

    n + 2n + 3n + ... + n^2 ≥ [n/2]^2 + ... + (n - 1)^2 + n^2
    I don't understand this line. How many terms are in the right-hand side? What is the term following [n/2]^2? Is it (n/2 + 1)^2? Further, how do terms on the left relate to those on the right, e.g., is n supposed to dominate (n/2)^2? The inequality n ≥ (n/2)^2 holds only for n <= 4.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Apr 2013
    From
    Australia
    Posts
    6

    Re: Finding Theta Question (upperbound)

    I'm not quite sure to be honest. I tried follow this example in my textbook

    1^k + 2^k + ... + n^k n^k + n^k + ... + n^k = n x n^k = n^k+1 for all n 1; hence
    1^k + 2^k + ... + n^k = O(n^k+1)

    1^k + 2^k + ... + n^k [n/2]^k + ... + (n-1)^k + n^k
    1^k + 2^k + ... + n^k [n/2]^k + ... + [n/2]^k + [n/2]^k
    1^k + 2^k + ... + n^k = [(n + 1)/2][n/2]^k (n/2)(n/2)^k = n^k+1 / 2^k+1 for all n 1.
    1^k + 2^k + ... + n^k = Ω(n^k+1)

    1^k + 2^k + ... + n^k = Ө(n^k+1)

    Did I not follow this correctly? lol
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,561
    Thanks
    785

    Re: Finding Theta Question (upperbound)

    Quote Originally Posted by Herblore View Post
    1^k + 2^k + ... + n^k ≥ [n/2]^k + ... + (n-1)^k + n^k
    Ah, here we remove the first half of the sum and leave the second one starting with [n/2]^k, where [n/2] apparently denotes n/2 rounded up. The number of remaining terms is n/2 if n is even and (n+1)/2 if n is odd, i.e., at most (n+1)/2.

    If you do the same thing with n + 2n + 3n + ... + n^2, you'll get

    n + 2n + 3n + ... + n^2 ≥
    [n/2] * n + ([n/2] + 1) * n + ... + n * n ≥
    [n/2] * n + [n/2] * n + ... + [n/2] * n ≥
    [n/2] * n * (n + 1) / 2
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Newbie
    Joined
    Apr 2013
    From
    Australia
    Posts
    6

    Re: Finding Theta Question (upperbound)

    Quote Originally Posted by emakarov View Post
    Ah, here we remove the first half of the sum and leave the second one starting with [n/2]^k, where [n/2] apparently denotes n/2 rounded up. The number of remaining terms is n/2 if n is even and (n+1)/2 if n is odd, i.e., at most (n+1)/2.

    If you do the same thing with n + 2n + 3n + ... + n^2, you'll get

    n + 2n + 3n + ... + n^2 ≥
    [n/2] * n + ([n/2] + 1) * n + ... + n * n ≥
    [n/2] * n + [n/2] * n + ... + [n/2] * n ≥
    [n/2] * n * (n + 1) / 2

    Thanks, I appreciate you trying to help me understand but I'm not sure why you've removed all the powers of n (n^k) and replaced them by just multiplying n. Shouldn't you be multiplying by n^2 or making it to the power of n^k which is 2 in this case like in the example?

    For example

    n + 2n + 3n + ... + n^2 ≥
    [n/2]^2 + ([n/2] + 1)^2 + ... + n * n^2 ≥
    [n/2]^2 + [n/2]^2 + ... + [n/2]^2 ≥
    [n/2]^2 * (n + 1) / 2
    = Ω(n^3)
    ?

    Jesus I'm confused lol.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,561
    Thanks
    785

    Re: Finding Theta Question (upperbound)

    Quote Originally Posted by Herblore View Post
    For example

    n + 2n + 3n + ... + n^2 ≥
    [n/2]^2 + ([n/2] + 1)^2 + ... + n * n^2
    This inequality is supposed to be obtained by removing the first half of the terms in n + 2n + 3n + ... + n^2. (At least the inequality 1^k + 2^k + ... + n^k ≥ [n/2]^k + ... + (n-1)^k + n^k in post #5 is obtained in this way.) Let's assume that n is even for simplicity. Obviously, if we remove the first n/2 terms from n + 2n + 3n + ... + n^2, the result is going to be ≤ the original sum. The removed terms are n + ... + (n/2)n, and the remaining terms are (n/2+1)n + ... + n^2. Therefore, the inequality is

    n + 2n + 3n + ... + n^2 ≥ (n/2+1)n + ... + n^2.

    (This is not exactly the same as in post #6, where the first terms on the right is [n/2]n, but I think this is cleaner.)

    The problem with your version in the quote above is that it is not clear why (n/2 + 1)^2 from the right-hand side occurs in the left-hand side at all. And n * n^2 = n^3 definitely does not occur in the left-hand side. Therefore, you cannot say that the inequality holds because the right-hand side is the sum of some subset of terms from the left-hand side.
    Thanks from Herblore
    Follow Math Help Forum on Facebook and Google+

  9. #9
    MHF Contributor
    Prove It's Avatar
    Joined
    Aug 2008
    Posts
    11,829
    Thanks
    1602

    Re: Finding Theta Question (upperbound)

    Quote Originally Posted by Herblore View Post
    Okay so I understand how to find the upperbound and lowerbound and hence theta for some simple functions like 4n + 5nlgn + 6 but what I don't understand is how to do it for the following function

    1 + 2 + ... + n

    I understand to find the upperbound you do the following steps

    1 + 2 + ... + n ≤ n + n + ... + n x n = n^2 for all n ≥ 1

    I understand why we substitute n but where does the n x n come from? (I got this example out of my text book)

    I want to know this so I can solve

    n + 2n + 3n + ... + n^2

    I believe I would do something like this

    n + 2n + 3n + ... + n^2
    ≤ n^2 + n^2 + n^2 + ... + n^2 x n^2 = n^4 for all n ≥ 1?
    Or is it
    n + 2n + 3n + ... + n^2 ≤ n^2 + 2n^2 + 3n^2 + ... + n^2 x n^2 = ??? for all n ≥ 1?


    Also, is the upperbound n^4 or am I not on the right track at all?

    Basically I'm just trying to figure out how to find the upperbound at the moment and then I will attempt to find the lowerbound. I've been puzzling over this for a while and would really appreciate it anyone could help.

    Thanks.
    I don't really understand why you are wanting to find upper bounds when these sums can be evaluated exactly quite easily.

    \displaystyle \begin{align*} 1 + 2 + 3 + \dots + n = \frac{n}{2} \left( 1 + n \right) \end{align*}

    and so

    \displaystyle \begin{align*} n + 2n + 3n + \dots + n^2 &= n \left( 1 + 2 + 3 + \dots + n \right) \\ &= n \left[ \frac{n}{2} \left( 1 + n \right) \right] \\ &= \frac{n^2}{2} \left( 1 + n \right)  \end{align*}
    Thanks from Herblore
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 2
    Last Post: November 26th 2010, 08:51 PM
  2. upperbound on expected value
    Posted in the Statistics Forum
    Replies: 2
    Last Post: May 31st 2010, 07:45 AM
  3. Replies: 2
    Last Post: March 29th 2010, 07:38 AM
  4. Finding the radius, solving, and finding theta?
    Posted in the Trigonometry Forum
    Replies: 2
    Last Post: June 13th 2009, 03:37 PM
  5. comparison test with 0 as upperbound
    Posted in the Differential Geometry Forum
    Replies: 3
    Last Post: February 26th 2009, 09:39 PM

Search Tags


/mathhelpforum @mathhelpforum