开发者

proving big o for a given equation

I would just like to prove the following: Show that 1^k + 2^k+...+n^k is O(n开发者_JS百科^(k+1)) for every positive integer k

I am not sure how to go about it. Normally when I am proving a function is big O of another function I find constants c,k such that f(x)<=cg(x) for all x>k. I don't think that this approach would work in the above example.


 1^k + 2^k+...+n^k <= n^k + n^k + .... + n^k = n * n^k = n^(k+1) 
0

上一篇:

下一篇:

精彩评论

暂无评论...
验证码 换一张
取 消

最新问答

问答排行榜