Problem:You’re given the following sequence:Write an algorithm with complexity O( log(n) ) to get the value of S.Solutions:1) the naive algorithm with a complexity O(n)#include <iostream>

using namespace std;

int main() {

// read the value of “a” and “n”..

long long a, S, A;

int n, i;

cin >> a >> n;

int fct = 1;

S = 0, A = a;

for(i = 0; i < n; i++) {

S += (fct * A);

A *= a, ++fct;

}

cout << S << “n”;

}2) faster algorithm with time complexity O(log(n)):we can get the value of S using the following formula:here’s the code:#include <iostream>

using namespace std;

long long power(long long a, int p) { //this function complexity is O(log(n))

long long res = 1;

while(p) {

if(p & 1)

res *= a;

a *= a;

p >>= 1;

}

return res;

}

int main() {

// read the value of “a” and “n”..

long long a, S, An, An1;

int n;

cin >> a >> n;

if(a == 1)

S = (n * (n + 1)) >> 1;

else {

An = power(a, n); // value of a^n

An1 = An * a; // value of a^(n + 1)

S = (((a * (1 – An)) / (1 – a)) – n * An1) / (1 – a);

}

cout << S << “n”;

}here’s the proof of the above formula:This problem is an exercise in Competitive programming book Edition 3,page [193].