无法计算函数的增长率

Question

您好，我正在尝试解决上面图片中的问题，但我不能。

特别是，我的问题是关于图像中的C（n），最后我得到了“7logn + n ^（1/3）”。 （证人c = 1，k = 7）“和+符号的右侧，”n ^（1/3）“， < = n“。

从我的角度来看，+符号之间的双方都是O（n），因此整个C（n）是O（n）。

但为什么答案是Big-theta（n^1/3）？

Answer 1

只有当log是基数2的对数（然后log（8）= 3，因为2^3 = 8），这才是真的。 （1/9）=（n^3）（12）（log（n）/ 9）=（8loglog（n））^（1/9）=（n^log（8））^ ^（1/9）= n ^（3 * 1/9）= n ^（1/3）

n ^（1/3）与n的第3根相同。

这是O（n ^（1/3）），而不是为O（log（n））的，因为前者长期的增长速度：实现的log（n）/（N的无限正

限制^（1/3））等于0.如果你必须切换表达式得到0，那么另一个将会增长得更快。例如。 n + log（n）将是O（n），因为n增长得更快，不会与n * log（n）（它是O（n * log（n））混淆。