- #1
mr_coffee
- 1,613
- 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:
1^3+2^3+3^3+...+n^3 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 that's 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?
note:
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).
Thanks!
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:
1^3+2^3+3^3+...+n^3 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 that's 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?
note:
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).
Thanks!
Last edited: