How to calculate tight bounds for asymptotic computational complexity for functions with subroutines?

Question

I am faced with this question related to computational complexity and Big O notation. I am having a hard time understanding how the subroutines influence the total complexity of the functions. Do I consider the subroutine with the highest complexity as the upper tight bound of the function, or do I have to calculate a sort of combined complexity? Here is the question:

"The functions c and d call subroutines a1, a2 and a4 with the following computational complexities:

a1 = O(n), a2 = O(n³) and a3 = O(n log n).

void c(int n) {
        int z = 0;
        if (a1(n)+a2(n)*a3(n) > 1)
            z = 1 + a1(n);
       return z;
    }
    
void d(int n) {
        int i, j, s = 0;
        for (i=0; i<n; i++)
            for (j=0; j<n; j++)
                s = s + a3(n);
        return s;
    }

Select tight bounds for the asymptotic computational complexity of functions c and d.

a) c = O(n⁶ log n) and d = O(n²)

b) c = O(n⁴ log n) and d = O(n³ log n)

c) c = O(n³) and d = O(n³ log n)

d) c = O(n⁴) and d = O(n³ log n)

e) c = O(n³) and d = O(n² log n)

f) c = O(n⁴ log n) and d = O(n²)"

Thank you in advance for the help!

Screenshot of the problem

Answer 1

First, note that in

void c(int n) {
    int z = 0;
    if (a1(n)+a2(n)*a3(n) > 1)
        z = 1 + a1(n);
    return z;
}

there is no loop. To evaluate the function you have to evaluate each of a1, a2, and a3 once and possibly evaluate a1 once more. Since your evaluating each function basically once, the time complexity of the function comes down to the time complexity of the subroutine with the worst performance, a2 which is O(n^3).

While in

void d(int n) {
    int i, j, s = 0;
    for (i=0; i<n; i++)
        for (j=0; j<n; j++)
            s = s + a3(n);
    return s;
}

you have a loop, that will iterate O(n^2) times, and in each iteration you are calling a function that takes O(n log n) time. We therefore multiply the time complexities yielding O(n^3 log n) (because we are going to be doing something that takes O(n log n) seconds, say, O(n^2) times).