Java 101 Chapter 4

In the following story we will discuss some algorithms and their execution time

Exercise #1

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

Since we only iterate through 0 until b, being b the value of the second variable, this algorithm is in order O(b). On space complexity it is constant since it only use one variable.

Exercise #2

int power(int a, int b) { 
    if (b < 0) {
        return 0; //error 
    } else if (b == 0) { 
        return 1; 
    } else { 
        return a* power(a, b - 1); 
    }
}

This is a recursive function where we iterate from b to 0. On this case, we have an execution time order of O(b)

Exercise #3

int sqrt(int n) {
 return sqrt_helper(n, 1, n); 
}
int sqrt_helper(int n, int min, int max) { 
    if (max < min) return -1; //no square root 
    int guess = (min + max)/2;
    if (guess *guess == n) { // found it! 
        return guess; 
    }
    else if (guess * guess < n) { //too low 
        return sqrt_helper(n, guess + 1, max); //try higher 
    } else { //too high 
        return sqrt_helper(n, min, guess - l); //try lower 
    }
}

Since we start calculating value between 1 and n, and after that we go either n/2 — n or 1 — n/2 we can say this is a O(log n) solution. It is constantly dividing by two the possible options.

Exercise #4

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

0( log n). The runtime will be the number of digits in the number. A number with d digits can have a value up to 10^d. If n = 10^d , then d = log n. Therefore, the runtime is 0( log n).