I am trying to find complexity for following algorithm. It is from "The Algorithm Design Manual" book.

for k = 1 to n:
   x = k
   while (x < n):
      print ’*’
      x = 2x

I simulated algorithm for some values. Each time inner loop operates on n-k value.

k=1
   x=1
   x=2
   x=4
   x=8
   ...
k=2
   x=2
   x=4
   x=8
   x=16
k=3
   x=3
   x=6
   x=12

And I do think that it has complexity of

$\sum\limits_{k=1}^{n}k*\lg(n-k)$

What do you think?

I am trying to find complexity for following algorithm. It is from "The Algorithm Design Manual" book.

for k = 1 to n:
   x = k
   while (x < n):
      print ’*’
      x = 2x

I simulated algorithm for some values. Each time inner loop operates on n-k value.

k=1
   x=1
   x=2
   x=4
   x=8
   ...
k=2
   x=2
   x=4
   x=8
   x=16
k=3
   x=3
   x=6
   x=12

And I do think that it has complexity of

$\sum\limits_{k=1}^{n}k*\lg(n-k)$

What do you think?

Edit 1

After some time, I think it should be $\sum\limits_{k=1}^{n}\lg(n-k)$