2
$\begingroup$

I have this algorithm which i have to convert to polynom of degree 2:

Algorithm is :

input n;
a <- -3;
b <- 5;
for i <- 1 to n do
   a <- a+3;
   b <- 2*a+b;
done;
output b;  

I already figured out that the resulting polynom for $n>0$ is :

$f(n) = 3n^2-3n+5$

I want to ask if there if this way of figuring out is right under all circunstances:

First let try to write a table for different $n>0$

 n | f(n)  | dfn/dn |   (dfn/dn)/dn
 1 |  5    |    -     |     -
 2 | 11    |    6     |     -
 3 | 23    |   12     |     6
 4 | 41    |   18     |     6
... ...       ...          ...

It looks that every quadratic polynoms can be expressed in this table so that the last table columns is a Constant Function which is something like second derivative of f(n) isn't it?? I then saw, then function can be written as: $$ f(n) = 5 + \sum_{i=1}^{n-1}6i = 5 + 6\ \sum_{i=1}^{n-1}i =3n^2 - 3n + 5$$

which is my final formula.

I want to ask.. is there any trick how to "extract" all coefficients out of table ??

$\endgroup$
1
$\begingroup$

For a quadratic $f(n)=an^2+bn+c$, you only need three values of the function to determine all coefficients. Since it's a polynomial, you can run your algorithm for any three $k$ integers. Let's use $n=1,2,3$.

$$f(1) = a + b + c$$ $$f(2) = 4a+2b+c$$ $$f(3) = 9a + 3b+ c$$

While it's straightforward to solve this system directly for $a,b,c$, once you have one value the rest are easily calculable using the equations themselves. We'll solve the simpler system:

$$5a+b = f(3)-f(2)$$ $$3a+b=f(2)-f(1)$$

Subtract the equations to find $a$ first.

$$a=\dfrac{f(3)-2f(2)+f(1)}{2}$$

Then

$$b = f(2)-f(1)-3a \,\,\,\, \text{ and } \,\,\,\, c = f(1)-a-b$$

Now you have your quadratic and can fill out the entire table.

In your case,

$$a= \dfrac{23-2(11)+5}{2}=\boxed{\color{red}3}$$ $$ b=(11-5-3(\color{red}3)) = \boxed{\color{blue}{-3}}$$ $$c= 5-(\color{red}3)-(\color{blue}{-3})=\boxed{\color{green}5}$$

edit: Here is a javascript implementation of the process: https://js.do/daveyp225/386868

$\endgroup$
  • $\begingroup$ I want to ask.. Because this algortihm is running in steps in range(1..n) why you say it stinks to start with 1 ?? I think it's the best option isn't it?? $\endgroup$ – Patrik Bašo Dec 30 '19 at 9:30
  • 1
    $\begingroup$ I just meant there are better options for the values of $f$, but the loop restricts our choices to $n\ge 1$. If the loop went from $-1$ to $n-2$ the solution here would be "prettier" $\endgroup$ – David Peterson Dec 30 '19 at 14:25
  • $\begingroup$ Ahh right I know what you mean now, Thank you $\endgroup$ – Patrik Bašo Dec 30 '19 at 15:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.