Können Sie mir erklären, wie man dafür Zeitkomplexität findet?

sum=0;
for(k=1;k<=n;k*=2)
  for(j=1;j<=k;j++)
     sum++;

Ich weiß also, dass die äußere Schleife eine zeitliche Komplexität von O (logn) hat, aber da die Iterationen der inneren Schleife vom Wert der äußeren Schleife abhängen, ist die Komplexität dieses Algorithmus nicht O (nlogn).

Das Buch sagt, es ist O (n).

Ich verstehe wirklich nicht, wie es ist O (n) ... Kann jemand bitte erklären ... Ich bin wirklich dankbar, wenn Sie in die Details gehen könnten, btw: D

Eine mathematische Lösung würde mir helfen, besser zu verstehen ...