Computational complexity – Examples

Algorithm

void calcSum(int[] array)
{
    int sum = 0;

    for (int i = 0; i < array.length; ++i)
    {
        sum += array[i];
    }
}

Solution
– Analysis: L3: Θ(1), L5: Θ(n), L7: Θ(1)
– Calculation: Θ(1) + Θ(n) * Θ(1) = Θ(n)

Algorithm

void calcSumAndProd(int[] array)
{
    int sum = 0;
    int prod = 0;

    for (int i = 0; i < array.length; ++i)
    {
        sum += array[i];
    }

    for (int i = 0; i < array.length; ++i)
    {
        prod = (prod == 0 ? prod + array[i] : prod * array[i]);
    }
}

Solution
– Analysis: L3: Θ(1), L4: Θ(1), L6: Θ(n), L8: Θ(1), L11: Θ(n), L13: Θ(1)
– Calculation: Θ(1) + Θ(1) + Θ(n) * Θ(1) + Θ(n) * Θ(1) = Θ(2n) = Θ(n)

Algorithm

void printCartProd(int[] array)
{
    for (int i = 0; i < array.length; ++i)
    {
        for (int j = 0; j < array.length; ++j)
        {
            println(array[i] + "," + array[j]);
        }
    }
}

Solution
– Analysis: L3: Θ(n), L5: Θ(n), L7: Θ(1)
– Calculation: Θ(n) * Θ(n) * Θ(1) = Θ(n²)

Algorithm

int binarySearch(int[] sortedArray, int low, int high, int goal)
{
    if (low <= high)
    {
        int mid = low + (high - low) / 2;
 
        if (goal == sortedArray[mid]) {
            return mid;
        }
        else if (goal < sortedArray[mid]) {
            return binarySearch(sortedArray, low, mid - 1, goal);
        } else {
            return binarySearch(sortedArray, mid + 1, high, goal);
        }
    }

    return -1;
}

Solution
Best case: First check is successful. → Goal is in the mid of the tree.
– Calculation: Θ(1)

Worst case: Last check is successful. → Goal is not in the tree at all.
– Calculation: Θ(depth) = Θ(log(n))