So_Cold's blog

Formula
By So_Cold, history, 8 years ago, In English 
for i = 1 to n 
    ans+=pow(x,i)

can it calculated in less than o(n) ? thanks in advance

  • Vote: I like it
  • +7
  • Vote: I do not like it

Comments Comments (2)
| Write comment?
»
8 years ago, # |
← Rev. 2   Vote: I like it +2 Vote: I do not like it

link

Also you can do it preety easily in .

→ Reply
»
8 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

This is the sum of a geometric series so it can be calculated fast by divide and conqueror approach.

Let n = 2k then y = x1 + x2 + ... + xk, and then the sum is y + xk * y.

→ Reply