I'm trying to solve a BigΘ problem, and could use a little guidance to make sure I'm on the right path.
So my question is to show that $\sum_{i=1}^{n} i^{15} = Θ(n^{16})$
I know that for something to be BigΘ it needs to be BigO and BigΩ, these are my definitions for each:
BigO Definition: $(∃K,C>0)(∀n>K)f(n)<=C∗g(n)$
BigΩ Definition: $(∃K,C>0)(∀n>K)f(n)>=C∗g(n)$
- Step 1) solve for BigO
So I need to prove that $\sum_{i=1}^{n} i^{15} <= C* (n^{16})$ for all n > K
I choose K = 1, C = 1
$\sum_{i=1}^{n} i^{15} <= (1) * (n^{16})$ for all n > 1
I choose n = 2
$\sum_{i=1}^{2} i^{15} <= (2^{16})$
$ 32769 <= 65536 $ which is true, and will be true for all n >1, thus BigO is proven.
- Step 2) solve for BigΩ [ where I mess up ]
So I need to prove that $\sum_{i=1}^{n} i^{15} >= C* (n^{16})$ for all n > K
I choose K = 1, C = 1
$\sum_{i=1}^{n} i^{15} >= (1) * (n^{16})$ for all n > 1, which will always be false, ok.. so need to make RHS smaller.
I choose K = 1, C = .1 [ is this allowed? to choose a decimal point for C? My only restriction is that C > 0.
$\sum_{i=1}^{n} i^{15} >= (.1) * (n^{16})$ for all n > 1
I choose n = 2
$\sum_{i=1}^{2} i^{15} >= (.1) * (2^{16})$
$ 32769 <= (.1) 65536 $
$ 32769 <= 6553.6 $ which is true, and will always be true.