Question

The task was to find the recurrence relation for this function and then find the complexity class for it as well. Provided is my work and the function. My question is, I feel like I'm missing some step in the recurrence relation and complexity class. Is this correct? The following code is in JavaScript.

function divideAndConquerSum(x){
if(x.length<1){
return 0;
}
if(x.length == 1){
return x[0];
}
var third = Math.floor((x.length-1)/3);
var next = (third *2)+1;
var y = x.slice(0, third+1);
var z = x.slice(third+1, next+1);
var a = x.slice(next+1, x.length);
return divideAndConquerSum(y)+divideAndConquerSum(z)+divideAndConquerSum(a);
  
}

///

work:

1. Checks if the array has length of zero...this is a constant time so : +1

2. Checks if the array has a length of 1, if so then return. Also constant time: +1

3. Splits the array into 3 parts this is also constant no matter the size of n: +1

4. Function then adds its self three times but each time is a recursive call of 1/3 the size of n: 3T(1/3)

1+1+1+ 3T(1/3)

3T(1/3)

calls itself so we can define the relation as

3T(1/3)

9T(1/9)

27T(1/27)

this pattern can shown as

3log₃n

so we have

1+1+1+ 3log₃n

which is a complexity class of

O(log n)

Answer 1

`Hey,

Note: Brother in case of any queries, just comment in box I would be very happy to assist all your queries

Since at every step the assigning is somewhat constant c

So, T(n)=3+3+3*T(n/3)=T(n/3)+6

Since 3 for assigning the first 3 assignment, next 3 for assigning value of function returned to variables.

Also T(1)=1

Consider n=3^k

So,

T(n)=3*(3*T(n/9)+6)+6=(3^2)*T(n/6)+6*(1+3)

T(n)=(3^3)*(T(n/27))+6*(1+3+3^2)

Lets say it end after k iteration then

T(n)=(3^k)*T(n/3^k)+6*(1+3+3^2+....3^(k-1))

So,

k=log3(n)

T(n)=n*T(1)+6*(1+3+....k terms)

So,

T(n)=n+6*(3^k-1)/2=3*(n-1)+n=4n-3

So,

T(n)=theta(n)

Kindly revert for any queries

Thanks.