Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Confused on Theta notation

  1. Nov 25, 2006 #1
    Hello everyone, have a problem. I'm not allowed to use the books instructions on how to do the problem but instead I must do the following:
    Prove each statement, assuming n is a variable that takes positive integer values.
    Ignore the book's instructions for 41. Instead, use the definition of Theta notation and work with inequalities. Since everything is positive, you don't need to use absolute values. Doing the exercise this way is a requirement, not a suggestion. (The following hint, however, is just a suggestion. For the lower bound, consider the sum of the series from the middle to the end, and find a lower bound on that.)

    The problem is the following:
    [tex]1^3+2^3+3^3+....+n^3[/tex] is Theta(n^4).

    The book only gives examples of inequalities, but this isn't, i'm not sure how to transform this into an inequality, does anyone know how to do this or have a website that will explain the process?

    Also he says find the lower bound, consider the sum of the series from the middle to the end, what is the middle? if the first term is 1 and the last is n^3 is he saying, use (1+n^3)/2? But thats just the average, not middle to the end so i'm also confused on that.
    I see this is a geometric progression, with a ratio of 3...so i could find a formula for the sum if i use the following:
    ratio: 3
    first term: 1
    mythical next term: 3 * n^3
    hm...maybe this isn't a geometric progression because usually the mythical next term doesn't have an n in the base but on the exp. But clearly each term is mutliplied by a ratio.

    Any ideas?

    definition of theta is the following:
    Definition (big-theta): Let f and g be functions from the set of
    integers (or the set of real numbers) to the set of real numbers. Then
    f(x) is said to be Theta( g(x) ), which is read as f(x) is big-theta
    of g(x), if f(x) is O( g(x) ), and Omega( g(x) ). We also say that
    f(x) is of order g(x).

    Last edited: Nov 25, 2006
  2. jcsd
  3. Nov 25, 2006 #2


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Invoke the definition of theta. (and then of O and of Omega)

    Your sum consists of n terms:

    1³, 2³, 3³, ..., (n-1)³, n³

    "middle" refers to the middle of this list.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook