Para evitar problemas sintacticos, o de como se escriben en java, se usará pseudo lenguaje, queda propuesto para ustedes pasarlos a java

Problema 1: Separar los elementos >0 y <=0 en un arreglo

Para hacerlo más general pensemos en la función:

arregloInteger separar (arregloInteger datos, integer marca);

que la invocamos con:

resultado= separar (datos, 0);

Invariante:
Si es menor lo dejamos tal cual e incrementamos en 1 el indice de búsqueda de menores,
Si es mayor lo intercambiamos con el elemento en el índice de búsqueda de mayores, y decrementamos el índice de mayores

arregloInteger separar (arregloInteger datos, integer marca){
    int mayor, menor, aux;
    /* los indices van de 0 a n-1 */
    menor= 0;
    mayor= datos.largo - 1;
    /* ahora el trabajo sucio */
    while (menor != mayor ){
        if (datos[menor] < marca)
            menor++;
        else{
            /* intercambienos el elemento en datos[menor] con el elemento en datos[mayor] y decrementamos mayor */
            aux= datos[menor];
            datos[menor]= datos[mayor];
            datos[mayor]= aux;
            mayor--;
        }
    }
}

Tiempo:
Para los menores el costo es 1
Para los mayores el costo es 1*k
En promedio el costo es (k + 1)*n/2, ojo que es en promedio, ¿por qué?, demuéstrenlo :)
Hint: supongan que en promedio la mitad del arreglo es menor que 0 y la otra mitad es mayor que 0

Problema 2: Encontrar la subsecuencia de suma máxima MAXSUM dentro de un arreglo

OJO: la subsecuencia de tamaño 0 suma 0

Solución lenta:

La idea es que con fuerza bruta calcular la suma de todas las subsecuencias posibles, a memdida que la suma de la secuencia actual sea mejor que la máxima la reemplazamos y al final nos quedamos con la mayor

int MAXSUM (arregloInteger datos){
    integer estaSuma, sumaMax, mejorI, mejorJ, i, j, k;
    sumaMax= 0;
    mejorI= 0;
    mejorJ= 0;
    /* for No 1 */
    for (i=0; i<datos.largo; i++){
        /* for No 2 */
        for (j=i; j<datos.largo; j++){
            estaSuma= 0;
            /* for No 3 */
            for (k=i; k<j; k++){
                estaSuma= estaSuma + datos[k];
            }
            if (estaSuma > sumaMax){
                sumaMax= estaSuma;
                mejorI= i;
                mejorJ= j;
            }
        }
    }
    return sumaMax;
}

Tiempo:
Para simplificar el análisis veamos el peor caso
El for No 1 se ejecuta n veces
El for No 2 se ejecuta a lo más n veces
El for No 3 se ejecuta a lo más n veces

El for No 3 esta anidado en el for No 2 y este a su vez en el for No1, luego se multiplican los tiempos
este algoritmo toma O(n³), uf!!!

Solución rápida:

Sumamos elementos consecutivos, si la suma actual es mayor que la máxima la reemplazamos, pero si la subsecuencia actual suma menor que 0 movemos el indice inicial de la subsecuencia un espacio más adelante del que vamos revisando y recalculamos la suma actual

int MAXSUM (arregloInteger datos){
    integer estaSuma, sumaMax, mejorI, mejorJ, i, j;
    i=0;
    estaSuma=0;
    sumaMax= 0;
    mejorI= 0;
    mejorJ= 0;
    /* for No 1 */
    for (j=i; j<datos.largo; j++){
        estaSuma= estaSuma + datos [j];
        if (estaSuma > sumaMax){
            sumaMax= estaSuma;
            mejorI= i;
            mejorJ= j;
        }
        else if (estaSuma < 0){
            i = j + 1;
            estaSuma=0;
        }
    }
    return sumaMax;
}

Tiempo:
Les queda claro que el costo es O(n)?, noten que el for hace sólo una pasada por los datos y para cada iteración del for se realizan a lo más 6 operaciones entre sumas, comparaciones y asignaciones, con esto se puede decir que el costo es O(n*cte), lo que es igual a O(n).
 

Problema 3: Pintado de superficies irregulares

Mediante un método recursivo diseñe un método recursivo que permita colorear una superficie irregular.

Suponga que la superficie está compuesta por sólo una región.
Suponga que los puntos se definen como par (x,y).
Suponga que tienen la función frontera(x,y), que retorna verdadero si (x,y) está en la frontera y falso sino.
Suponga que conoce un punto al interior de la superfice.

Como referencia considere la figura.
 

Para pintar la figura, se comienza en el punto conocido y primero se prueba si se puede pintar arriba, luego a la derecha, abajo y por último a la izquierda.

Para indicar que un punto fue pintado se utiliza pinta(x,y), que se encarga de marcar (x,y) como un punto pintado.

Para evitar pintar dos veces un punto, se utiliza la función pintado(x,y) que retorna verdadero si (x,y) está pintado y falso si no.

La condición de borde se tiene cuando se encuentra un punto en la frontera o que ya está pintado.

/* La figura tiene el borde definido */
Figura es una matriz de MaxX x MaxY;

pintar (x, y) {
    /* condición de salida */
    if (fontera(x,y) o pintado(x,y)) {
        return;
    }
    /* acción */
    else {
        pinta(x,y);
    }
    /* llamadas recursivas hacia arriba, derecha, abajo e izquierda */
    pintar(x, y+1);
    pintar(x+1, y);
    pintar(x, y-1);
    pintar(x-1, y);
    return;
}

/* Funciones auxiliares */
frontera (x,y){
    if (Figura[x,y] = FRONTERA){
        return verdadero;
    }
    else {
        return falso;
    }
}

pintado(x,y){
    if (Figura[x,y] = PINTADO){
        return verdadero;
    }
    else {
        return falso;
    }
}

pinta(x,y){
    Figura[x,y] <- PINTADO);
}

Extensiones:

Contar los puntos a pintar:

Utilizando variables globales:

int contador <- 0;

pintar (x, y) {
    /* condición de salida */
    if (fontera(x,y) o pintado(x,y)) {
        return;
    }
    /* acción */
    else {
        pinta(x,y);
        Pintados++;
    }
    /* llamadas recursivas hacia arriba, derecha, abajo e izquierda */
    pintar(x, y+1);
    pintar(x+1, y);
    pintar(x, y-1);
    pintar(x-1, y);
    return;
}

Utilizando variables locales:

pintar (x, y) {
    int contador = 0;
    /* condición de salida */
    if (fontera(x,y) o pintado(x,y)) {
        return contador /* == 0 */;
    }
    /* acción */
    else {
        pinta(x,y);
        contador++;
    }
    /* llamadas recursivas hacia arriba, derecha, abajo e izquierda */
    contador = contador + pintar(x, y+1);
    contador = contador + pintar(x+1, y);
    contador = contador + pintar(x, y-1);
    contador = contador + pintar(x-1, y);
    return contador;
}

Problema 4: Calculo del factorial de un número

Existen maneras especialemente malas de ocupar la recursividad, una de ellas es el siguiente algoritmo:

int factorial (integer n){
    if (n = 0) or (n = 1) then
        return 1;
    else
        return n * factorial(n - 1);
}

El costo de este algoritmo es (estoy midiendo las multiplicaciones)

T(n) = T (n-1) + 1
T(0) = 1

=> T(n) = n

Costo de tiempo n, costo en memoria n, pero gasta mucha memoria al definir el espacio de variables locales para cada llamada recursiva de la función, esto se traduce en que la constante de uso de memoria es grande.

Noten que el siguiente algoritmo iterativo incremental también resuelve el problema

int factorial (integer n){
    fac[0]= 1;
    fac[1]= 1;
    for (int i= 2; i <= n; i++){
        fac[i]= i*fac[i-1];
    }
    return fac[n];
}

Y tiene costo n en tiempo y en memoria!!, (y la constante de uso de memoria es 1 :) )

Moraleja: "La recursión no siempre es la mejor solución"