What is the minimum number of steps needed to find the value of an nth order polynomial by making calls to a function that can compute the value of a 1st order polynomial (ax+b)? What is the answer if we can do parallel processing which allows us to call the function simultaneously any number of times?

Question

Accepted Answer

The minimum number of steps needed to find the value of an nth order polynomial is n+1.

To find the value of a 1st order polynomial, we need 2 steps (1 multiplication and 1 addition).
For an nth order polynomial, we need to compute n 1st order polynomials and perform n-1 additions.
Therefore, the minimum number of steps is n+1.
If parallel processing is allowed, we can compute the value of each 1st order polynomial simultaneously, reducing the time taken.
In this case, the number of steps remains the same, but the time taken is reduced due to parallel processing.

Qualcomm Research Intern interview questions & answers