Question

How would I write a program for C++ that checks if an entered string is an accepted polynomial and if it is, outputs its big-Oh notation? Accepted polynomials can have 3 terms minimum and no decimals in the exponents.

Answer 1

Aa polynomial of the form c_nxⁿ + c_n-1x^n-1 + c_n-2x^n-2 + … + c₁x + c₀

and a value of x, Here c_n, c_n-1, .. are integers (may be negative)

and n is a positive integer.

Input is in the form of an array = poly[]

where, poly[0] represents coefficient for xⁿ and poly[1] represents coefficient for x^n-1 and so on.

Example:-

#include <iostream>

using namespace std;

int horner(int poly[], int n, int x) {

int result = poly[0];

    for (int i=1; i<n; i++)

        result = result*x + poly[i];

return result;

}

int main()

{

    // Let us evaluate value of 2x3 - 6x2 + 2x - 1 for x = 3

    int poly[] = {2, -6, 2, -1};

    int x = 3;

    int n = sizeof(poly)/sizeof(poly[0]);

    cout << "Value of polynomial is " << horner(poly, n, x);

    return 0;

}

Result:-

Value of polynomial is 5

Time complexity is Big-Oh