在big-O表示法中O((log n)^k) = O(log n),k某些常量(例如,循环的对数),是真的吗？
我的教授告诉我,这种说法是正确的,但是他说这将在课程的后期证明.我想知道你们中是否有人能证明其有效性,或者有一个链接我可以确认是否属实.
(1)O(log(n ^ k))= O(log n)确实如此.
(2)O(log ^ k(n))(也写为O((log n)^ k))= O(log n)是错误的.
观察:(1)已被nmjohn证实.
练习:证明(2).(提示:f(n)= log ^ 2 n是O(log ^ 2 n).是O(log n)？什么是足够大的常数c,使得对于大于n 0的所有n,c log n> log ^ 2 n？)
编辑:
在相关的说明中,任何发现此问题有用和/或有趣的人都应该对新的"计算机科学"StackExchange网站表现出一些喜爱.这是一个链接.去把这个新的地方变为现实吧!