c*c的时间复杂度？

Question

这里有时间复杂性问题:

for i = 1 to n
    if something
        p = p*c
    c = c*c

对于第1行,时间复杂度应为n,但第3行和第4行呢？是n ^ 2？还是n ^ n？

Answer 1

算术运算,如乘法,被认为是O(1)(恒定时间),因此整个代码样本是O(n),因为有n恒定时间操作(O(1*n)).