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.

1 Attachment(s)

Re: Finding Theta Question (upperbound)

Hi,

For your first question:

; there are n terms in .

I think there must be a typo, there should be an = before the

So your second problem:

; again there are n terms in

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

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?

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.

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

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

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.

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.

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.

and so