如何计算该代码的时间复杂度

Question

null

null

T(n)=O(1)+O(nlogn)=O(nlogn)

但我不确定。有人能帮帮我吗。

Scanner sc = new Scanner(System.in);
System.out.print("Enter a number:");
int x = Integer.parseInt(sc.next());
for(int i=1 ; i<x; i*=2) {
  System.out.print("*");
  for(int j=0; j<i;j++) {
    System.out.print(" ");
  System.out.println("*");
}

Answer 1

正如您所发现的，时间复杂度是：

t(x)=1+2+4+...+2^{log(x)}

但是你在上面求和的结果中有一个错误。因为t(x)是因子2: