complexity-theory - BIG-O 证明解决

Question

我问了一个关于 Big-Oh / Big-Theta 的问题，但他们在其中获得了常数

它很大，并且没有任何可见的常数，所以我不知道从哪里开始，因为它是从 1 到 n 的 i^k 的总和。

如果有人可以告诉我如何开始使用它，将不胜感激。

谢谢你。

Answer 1

这个是这样的：

n= 1, 2,...
f(n)
    =   \sum_{i=1}^{n} i^k
    <=  \sum_{i=1}^{n} n^k
    =   n*(n^k)
    =   n^{k+1)

因此

f(n)  \in  O(n^{k+1})