# Finding Theta Question (upperbound)

• May 25th 2013, 04:28 AM
Herblore
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.
• May 25th 2013, 08:32 AM
johng
Re: Finding Theta Question (upperbound)
Hi,
$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$

$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.

Attachment 28452
• May 25th 2013, 11:11 PM
Herblore
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?

• May 26th 2013, 10:58 AM
emakarov
Re: Finding Theta Question (upperbound)
Quote:

Originally Posted by Herblore
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

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.
• May 26th 2013, 10:33 PM
Herblore
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
• May 27th 2013, 03:43 PM
emakarov
Re: Finding Theta Question (upperbound)
Quote:

Originally Posted by Herblore
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
• May 27th 2013, 10:46 PM
Herblore
Re: Finding Theta Question (upperbound)
Quote:

Originally Posted by emakarov
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.
• May 28th 2013, 12:42 PM
emakarov
Re: Finding Theta Question (upperbound)
Quote:

Originally Posted by Herblore
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.
• May 28th 2013, 07:23 PM
Prove It
Re: Finding Theta Question (upperbound)
Quote:

Originally Posted by Herblore
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*}