Let $k$ be a positive integer. Show that $1^k+2^k+...+n^k$ is $O (n^{k+1})$.
So according to the definition of big-$O$ notation we have:
$$1^k+2^k...+n^k ≤ n(n^k) = n^{k+1}$$
whenever $n>1$
Is this a satisfied answer? can someone help?
$\begingroup$
$\endgroup$
5
asked Apr 23, 2015 at 17:45
-
9$\begingroup$ That's a fine answer. $\endgroup$– Antonio VargasApr 23, 2015 at 17:47
-
$\begingroup$ If you just want big-O, then your answer is fine. If you want big-Theta (i.e. the sum is also lower bounded by $cn^{k+1}$ for some constant $c > 0$, that is a harder problem. Sometimes even professors confuse big-O and big-Theta, so make sure that all you have to do is big-O (upper bound). $\endgroup$– user2566092Apr 23, 2015 at 17:51
-
$\begingroup$ I suppose it is big-$O$. $\endgroup$– Alim TeacherApr 23, 2015 at 17:54
-
$\begingroup$ You know this thing is $\sim \frac{n^{k+1}}{k+1}$? $\endgroup$– ncmathsadistApr 23, 2015 at 18:17
-
$\begingroup$ I have this exact same question, but don't understand this (def not saying it's wrong - only it's too concise for novice and I don't get it). How does this prove it? Explaining it like I'm 5yrs old would be welcomed. $\endgroup$– Mote ZartOct 24 at 21:58
Add a comment
|