Problemas de complejidad java

Propiedades de los sumatorios
Los sumatorios son representaciones compacta de la forma
i=1i=nfi=f1+f2+…+fn
Algunas propiedades son:
i=ai=bfi+gi=i=ai=bfi+i=ai=bgii=ai=bj=cj=dfig(j)=i=ai=bf(i)j=cj=dg(j)
i=ai=bgfi=gi=ai=bfi, si g no depende de i
i=ai=bfi=i=1i=nf(i)-i=1i=a-1f(i)

Algunos sumarios usuales
i=ab1=b-a+1
i=0ni=n(n+1)2
i=0ni2=nn+1(2n+1)6i=0nik=c0ik+1+c1ik+…Θ(nk+1)
Otra notación para los sumatorios
En muchos casos es conveniente usar una notación más general para los sumatorios. En los casos anteriores la variable i toma valores de un conjunto de la forma{a,a+1,a+2,…,b}. A esto conjunto lo denominaremos por I[a,b]. Ahora permitiremos que la variable i tome valores escogidos de un conjunto de índices más general I. Esto lo expresaremos como:
i∈If(i)Por ejemplo
i∈I[a,b]fi=i=abf(i)
En muchos casos podemos transformar los sumatorios más generales en los más sencillos vistos arriba. Para hacerlo realizamos un cambio de variable. Veamos algunoscasos:
1. Sea el conjunto de índices I[a,b]={a,a+1,a+2,…,b} entonces el sumatorio
i∈I[a,b]fi=x∈I[0,s]fx+a=x=0b-af(x+a)
Donde i=a+x, x=i-a, s=b-a

2. Sea el conjunto de índicesI={a,a+r,a+2r,…,b} entonces el sumatorio
i∈Ifi=x∈I[0,s]fa+xr=x=0(b-a)/rf(a+xr)
Donde i=a+xr, x=i-ar, s=b-ar

3. Sea el conjunto de índices I={a,a-r,a-2r,…,b} entonces el sumatorioi∈Ifi=x∈I[0,s]fa-xr=x=0(a-b)/rf(a-xr)
Donde i=a-xr, x=a-ir, s=a-br

4. Sea el conjunto de índices I={a,ar,ar2,…,b} entonces el sumatorio
i∈Ifi=x∈I[0,s]farx=x=0logr(b/a)f(arx)
Donde i=arx, x=logr(i/a),s=logr(b/a)

5. Sea el conjunto de índices I={a,a/r,a/r2,…,b} con b>0 entonces el sumatorio
i∈Ifi=x∈I[0,s]far-x=x=0logr(a/b)f(ar-x)
Donde i=a+r-x, x=logr(a/i), s=logr(a/b)
En el caso de queb=0, entonces s=logra+1, y el sumatorio sería:
i∈Ifi=x∈I[0,s]far-x=x=0logra+1f(ar-x)
6. Sea el sumatorio definido sobre un conjunto de índices I y una restricción del tipo:
i∈I,...