Having problems with big oh, Omega, theta

Question

Show the following:

$\ $ (a) $\, \sum_{i=1}^n(3i+2n)\text{ is }O(n^2)$

$\ $ (b) $\, \sum_{k=1}^n(k/3)\text{ is }\Omega(n^2)$

$\ $ (c) $\, \sum_{j=1}^n\sum_{k=1}^n 7n\text{ is }\Theta(n^3)$.

Thank you.

I've copied the formulas from the picture. Please check them. For some basic information about writing math at this site see e.g. here — Américo Tavares, Mar 23 '13 at 18:31

score 2 · Accepted Answer · edited May 10 '13 at 16:35

2

The first sum can be separated, giving you $2n(n)+\sum_1^n 3i$, which gives you $2n^2+\frac32(n+1)n$. Clearly this is $\mathcal{O}(n^2)$. The rest are similarly straightforward.

Use the definitions.

edited May 10 '13 at 16:35

answered Mar 23 '13 at 18:32

Lepidopterist

2,751

Having problems with big oh, Omega, theta

1 Answers1