Ejercicios Big-O

Ejercicios

1

Este código computa el producto de dos variables, cuál es el runtime de este código?

int product(int a, int b) {
    int sum = 0;
    for (int I = 0; I < b; I++) {
        sum += a;
    }
    return sum; 
}

2

Este codigo computa A ^ B, cual seria el runtime?

static int power(int a, int b) {
    if (b < 0) return a;
    if (b == 0) return 1;
    int sum = a;
    for (int I = 0; I < b - 1; I++) {
        sum *= a;
    }
    return sum;
}

3

Este codigo computa A % B, cual seria el runtime?

int mod(int a, int b) {
    if (b <=a) return -1;
    int div = a / b;
    return a - div * b;
}

4

Este código computa una division entre números enteros (asumiendo que ambos son positivos), cuál seria el runtime?

int div(int a, int b) {
    int count = a;
    int sum = b;
    while (sum <= a) {
        sum += b;
        count++;
    }
    return count;
}

5

El siguiente código calcula la raíz cuadrada de un numero entero. Si el número no es un cuadrado perfectO(no hay raíz cuadrada entera), entonces devuelve -1. Lo hace mediante suposiciones sucesivas. Si N es 100, primero adivina si N es 50. ¿Demasiado alto? Pruebe algo más bajo, a mitad de camino entre 1 y 50 ,etc. ¿Cuál es el big-o?

int sqrt(int n) {
    return sqrt_helper(n, 1, n);
}
int sqrt_helper(int n, int min, int max) {
    if (max < min) return -1;
    int guess = (min + max) / 2;
    if (guess * guess == n) {
        return guess;
    } else if (guess *guess <n) {
        return sqrt_helper(n, guess + 1, max) ; 
    } else { 
        return sqrt_helper(n, min, guess - 1);
    }
}

6

El siguiente código calcula la raíz cuadrada de un número entero. Si el número no es un cuadrado perfecto (no hay raíz cuadrada entera), entonces devuelve -1. Lo hace intentando números cada vez más grandes hasta que encuentra el valor correcto (o es demasiado alto). ¿Cuál es su tiempo de ejecución?

int sqrt(int n) {
    for (int guess = 1; guess * guess < n; guess++) {
        if (guess * guess == n) return guess;
    }
    return -1;
}

7

Si un árbol de búsqueda binario (Binary Search Tree - BST) no está equilibrado, ¿cuánto tiempo podría en el peor de los casos tomar encontrar un elemento?

8

Cuál seria el peor de los casos si estamos buscando un valor en un árbol binario (Binary Tree - BT) que no esta ordenado?

9

El método appendToNew agrega un valor a un array creando una nueva array más larga y devolviendo esta array más larga. Cuánto tiempo lleva copiar el array?

int[] copyArray(int[] array) {
    int[] copy = new int[0];
    for (int value : array) {
        copy = appendToNew(copy, value);
    }
    return copy;
}
int[] appendToNew(int[] array, int value) {
    int[] bigger = new int[array.length + 1];
    for (int I = 0; I < array. length; I++) {
        bigger[I] = array[I];
    }
    bigger[bigger.length - 1] = value; 
    return bigger;
}

10

El siguiente código suma los dígitos de un número. Cuál es su tiempo de ejecución?

int sumDigits(int n) { 
    int sum = 0; 
    while (n > e) { 
        sum += n % 10; 
        n /= 10; 
    } 
    return sum; 
} 

11

El siguiente código calcula la intersección (el número de elementos en común) de dos Arrays. Asumiendo que ninguna Array tiene duplicados. Calcula la intersección ordenando la Array B y luego iterando a través de la Array A - haciendo una comprobación (mediante búsqueda binaria / Binary Search) si cada valor está en B. ¿Cuál es su tiempo de ejecución?

int intersection(int[] a, int[] b) { 
    mergesort(b);
    int intersect =0;

    for (int x : a) {
        if (binarySearch(b, x) >= 0) {
            intersect++;
        } 
    }

    return intersect;
}

Respuestas

1. O(B) Seria Linear runtime sobre B, ya que el loop solo itera sobre B.
2. O(B) Seria Linear runtime sobre B, ya que el loop solo itera sobre B.
3. O(1) Constant runtime
4. O(A/B) La variable count eventualmente sera A/B. El While loop eventualmente iterara lo mismo que A/B.
5. O(Log N) Este algoritmo en esencia esta haciendo un binary search para encontrar la raíz cuadrada.
6. O(Raíz Cuadrada(N)) O en ingles O(sqrt()N). Este es un simple loop que para cuando encontramos guess * guess > N. En otras palabras guess > sqrt(N).
7. O(N), en donde N es el numero de hojas en el árbol. El máximo tiempo posible seria la profundidad del árbol.
8. O(N) , sin ningún orden - tendríamos que buscar todos los nudos en el árbol.
9. O(n ^ 2) en donde N es el numero de elementos en el array.
10. O(Log N) El runtime seria la cantidad de dígitos en el numero.
11. O(B log B + A log B), Primero tenemos que ordenar la Array B - que conlleva B Log B. Después por cada elemento en Array A - haremos una búsqueda binaria en Log B, que quedaría como A Log B.