Confused on Theta notation

In summary: For n=odd, it is the (n+1)/2-th term, for n=even, it is the n/2-th term.In summary, The problem is to prove that 1³+2³+3³+...+n³ is Theta(n⁴), using the definition of Theta notation and working with inequalities. The book suggests finding a lower bound by considering the sum of the series from the middle to the end. However, it is unclear how to transform this problem into an inequality. The definition of theta is also mentioned, which involves O and Omega. The middle refers to the middle term of the series, which is (n+1)/2 for odd n and n/2 for even
  • #1
mr_coffee
1,629
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 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:
Physics news on Phys.org
  • #2
mr_coffee said:
i'm not sure how to transform this into an inequality
Invoke the definition of theta. (and then of O and of Omega)


what is the middle?
Your sum consists of n terms:

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

"middle" refers to the middle of this list.
 

1. What is Theta notation?

Theta notation, also known as asymptotic notation, is used to express the time complexity of an algorithm in terms of its input size. It is represented by the Greek letter Θ and provides an upper and lower bound for the algorithm's running time.

2. How is Theta notation different from Big O notation?

Theta notation provides a more precise measure of an algorithm's time complexity than Big O notation. While Big O notation only provides an upper bound for the running time, Theta notation gives both an upper and lower bound, making it a tighter and more accurate representation of an algorithm's efficiency.

3. How is the time complexity represented in Theta notation?

In Theta notation, the time complexity of an algorithm is represented as Θ(f(n)), where f(n) is a function of the input size n. This means that the algorithm's running time will grow at the same rate as f(n), within a constant factor.

4. What is the significance of the upper and lower bound in Theta notation?

The upper and lower bound in Theta notation provide a range of possible running times for an algorithm. This range gives a more accurate idea of the algorithm's efficiency compared to just using the upper bound in Big O notation, which may not be a precise measure.

5. How is Theta notation used in analyzing algorithms?

Theta notation is used in analyzing algorithms to compare their efficiency and determine which one is more optimal. By looking at the upper and lower bounds of an algorithm's time complexity, we can determine how it will perform as the input size increases and make informed decisions about which algorithm to use for a given problem.

Similar threads

  • Calculus and Beyond Homework Help
Replies
6
Views
275
  • Calculus and Beyond Homework Help
Replies
3
Views
467
  • Calculus and Beyond Homework Help
Replies
1
Views
533
  • Calculus and Beyond Homework Help
Replies
1
Views
452
  • Calculus and Beyond Homework Help
Replies
1
Views
414
  • Calculus and Beyond Homework Help
Replies
3
Views
762
  • Calculus and Beyond Homework Help
Replies
7
Views
653
  • Calculus and Beyond Homework Help
Replies
3
Views
488
  • Calculus and Beyond Homework Help
Replies
3
Views
637
  • Calculus and Beyond Homework Help
Replies
9
Views
1K
Back
Top