# Horner’s Rule and Recurrence Relation

Contents

## Introduction

In this article, we are going to have a look at Horner’s Rule and Recurrence Relation.

The `taylor` function takes the same three parameters as before: `x`, `a`, and `n`. It uses a static variable `sum` to store the current sum of the Taylor Series. The base case of the recursion is when `n` is zero, in which case the function returns the current value of `sum`.

The recursive step of the function calculates the next term of the Taylor Series using the formula for the `n`th derivative of the `sin(x)` function evaluated at `a`. The function then adds this term to the previous sum of the Taylor Series using the `sum` variable. Finally, the function calls itself recursively with the smaller subproblem of `n-1`.

Horner’s Rule is used to evaluate the polynomial `1 + ((x-a)^2/2!) + ((x-a)^4/4!) + ((x-a)^6/6!) + ...`. The `for` loop in the function iterates from `n` down to `1`, factoring out the `x-a` term from each subsequent term of the polynomial and adding it to the previous sum of the Taylor Series using the `sum` variable.

## Recurrence Relation

Recurrence Relation is a mathematical concept that defines a sequence in terms of its previous terms. Recurrence Relations are used to model many real-world phenomena, such as the growth of population and the spread of infectious diseases. In the context of Taylor Series, Recurrence Relations can be used to calculate the time complexity of the recursive functions.

Let’s consider the following Recurrence Relation for the Taylor Series of the `sin(x)` function using recursion:

``````T(n) = T(n-1) + O(1)
``````

where `T(n)` is the time complexity of the `taylor` function with `n` terms in the Taylor Series, and `O(1)` represents the time complexity of the constant operations in the function. The base case of the recursion is `T(0) = O(1)`.

Using the Recurrence Relation, we can calculate the time complexity of the `taylor` function using the following formula:

``````T(n) = T(n-1) + O(1)
= T(n-2) + O(1) + O(1)
= T(n-3) + O(1) + O(1) + O(1)
= ...
= T(0) + O(n)
= O(n)
``````

Thus, the time complexity of the `taylor` function using recursion is `O(n)`, where `n` is the number of terms in the Taylor Series.

See also  SUM OF THE NATURAL NUMBERS USING RECURSION and FACTORIAL USING RECURSION￼

## Conclusion

In conclusion, Taylor Series is a powerful tool in calculus that approximates any continuous and differentiable function as an infinite sum of powers of `x`. Recursion and Horner’s Rule are two methods that can be used to calculate the Taylor Series of a function. Recursion uses a function that calls itself with smaller subproblems until a base case is reached, while Horner’s Rule reduces the number of multiplications needed to evaluate a polynomial. Recurrence Relations can be used to calculate the time complexity of the recursive functions. Understanding the concepts of Taylor Series, recursion, and recurrence relations is essential for students of mathematics, engineering, physics, and other sciences.