STRUCT CA3 The purpose of this assignment is to write an algorithm, in pseudocod
ID: 3752721 • Letter: S
Question
STRUCT CA3 The purpose of this assignment is to write an algorithm, in pseudocode form, to evaluate a polynomial at a given fixed-point. Let fx)- ant"nat t ao. Evaluate the function at x-p (1) Write an algorithm, in pseudocode form, for the above. The algorithm inputs are - values of n, p, All: output is -value of fp). (2) Identify the operations and number of each performed to producethe output. (3) Express your algorithm's complexity as a function of n. Hint: (i) Consider an instance of a polynomial. Let n#5,p-3, and A0-(8,5,67,4,9). The instance of the above polynomial can be expressed as fx) 8x+5x4+ 6x3 +7x2+ 4x +9. You have to compute f(3). Through this example identify the operations and the number of each that you perform to produce the output. (ii) Identify the complexity of your instance. (iii) Using your experience develop a mathematical expression of your algorithm's complexity for evaluating f(p). Not SubmittedExplanation / Answer
Pseudo COde:-
Operations:-
There are two operations performed-
1. Addition of previous value of f to current evaluated value.
2. Calculation power(p, n-i), it is multiplying p to itself, (n-i) times.
Complexity:-
Since there is only one loop that iterates through 0 to n, so the complexity of this pseudo code will be O(n).
If there is anything that you do not understand, then please mention it in the comments section.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.