这个函数的大O符号是什么？

Question

对于以下伪代码,最糟糕的时间复杂度大O符号是什么？(假设函数调用是O(1))我对大O表示法很新,所以我不确定答案但是我在考虑O(log(n)),因为while循环参数每次乘以2或者那只是O(loglog(n))？或者我错了两个方面？任何输入/帮助都是值得赞赏的,我正试图掌握大O符号的概念,因为我刚刚开始学习最糟糕的时间复杂度.谢谢!

i ? 1
while(i<n)
    doSomething(...)
    i ? i * 2
done

Answer 1

如果i每次都加倍,那么循环执行的次数是你i到达之前可以加倍的次数n.或者以数学方式编写它,如果x是循环执行的次数,我们有2^x <= n.求解x给出 x <= log_2(n).因此循环执行的次数是O(log(n))

Answer 2

i以指数方式增长,因此循环将在对数时间内完成,O(log(n))