MHB Two different algorithms for valuation of polynomial

[evinda]

Hello! (Wave)

The following part of code implements the Horner's method for the valuation of a polynomial.

$$q(x)=\sum_{i=0}^m a_i x^i=a_0+x(a_1+x(a_2+ \dots + x(a_{m-1}+xa_m) \dots ))$$

where the coefficients $a_0, a_1, \dots , a_m$ and a value of $x$ are given:

1.k<-0
2.j<-m
3.while (j>=0)
4.         k<-a_j+x*k
5.         j<-j-1

• Which is the asymptotic time complexity of this part of the code for the Horner's method?

I thought the following:

At the line [m]1[/m], [m] 1 [/m] command is executed.
At the line [m]2[/m], [m] 1 [/m] command is executed.
The line $3$ is executed [m] m+1 [/m] times.
The line [m]4[/m] is executed [m] 3m [/m] times.
The line [m]5[/m] is executed [m] 2m [/m] times.

So, the time complexity of the part of the code is $O(m)$.

Is it right? How could I formulate it better? (Thinking)

• Write a pseudocode for the implementation of the simple algorithm of valuation of a polynomial, that calculates each term of the polynomial independenlty from the others.
  Which is the time complexity?
  Compare it with the correspong time complexity for the Horner's method.

So does this mean that we have to do something like that?

k<-0
l<-0
i<-m
while j>=0
        l=pow(x,j)*a_j;
        k+=l;
        j-=1;

Or have I understood it wrong?

 

[alyafey22]

I thought the following:

At the line [m]1[/m], [m] 1 [/m] command is executed.
At the line [m]2[/m], [m] 1 [/m] command is executed.
The line $3$ is executed [m] m+1 [/m] times.
The line [m]4[/m] is executed [m] 3m [/m] times.
The line [m]5[/m] is executed [m] 2m [/m] times.

So, the time complexity of the part of the code is $O(m)$.

Is it right? How could I formulate it better? (Thinking)

You don't need to find the number of times every statement gets executed unless the question is to find the exact number of some atomic operations. In the case of complexity analysis we only care about the statements that get executed the most in that case the statements inside the for loop which at most runs in $O(m)$

So does this mean that we have to do something like that?

k<-0
l<-0
i<-m
while j>=0
        l=pow(x,j)*a_j;
        k+=l;
        j-=1;

Or have I understood it wrong?

It think it is correct but you write j instead of i and k can be omitted.

 

[evinda]

You don't need to find the number of times every statement gets executed unless the question is to find the exact number of some atomic operations. In the case of complexity analysis we only care about the statements that get executed the most in that case the statements inside the for loop which at most runs in $O(m)$

Ok... How could I justify it then formally that the time complexity is $O(m)$?

It think it is correct but you write j instead of i and k can be omitted.

Why can k be omitted? Are we only looking for the valuation of the terms of the polynomial seperately and not for the valuation of the polynomial? (Thinking)

 

[alyafey22]

Ok... How could I justify it then formally that the time complexity is $O(m)$?

Assume that additions and multiplications take constant time $c$ . Then the complexity of the algorithm is

$$\sum_{j=0}^m c = c(m+1) \in O(m) $$

Why can k be omitted? Are we only looking for the valuation of the terms of the polynomial seperately and not for the valuation of the polynomial? (Thinking)

What I meant is that

l<-0
j<-m
while j>=0
        l+=pow(x,j)*a_j;
        j-=1;

 

[evinda]

Assume that additions and multiplications take constant time $c$ . Then the complexity of the algorithm is

$$\sum_{j=0}^m c = c(m+1) \in O(m) $$

Like that we take only into consideration the commands that are executed inside the while-loop, right? (Thinking)

What I meant is that

l<-0
j<-m
while j>=0
        l+=pow(x,j)*a_j;
        j-=1;

I see.. So this pseudocode has also time complexity $O(m)$, right? (Thinking)

 

[alyafey22]

Like that we take only into consideration the commands that are executed inside the while-loop, right? (Thinking)

Yeah because others will run in constant time.

I see.. So this pseudocode has also time complexity $O(m)$, right? (Thinking)

You are evaluating the power inside the loop which must be considered , right ?

 

[evinda]

You are evaluating the power inside the loop which must be considered , right ?

So does the function [m]pow(x,j)[/m] have time complexity [m] O(j) [/m] ?

 

[alyafey22]

So does the function [m]pow(x,j)[/m] have time complexity [m] O(j) [/m] ?

It performs exactly j-1 multiplications to find the jth power.

 

[evinda]

It performs exactly j-1 multiplications to find the jth power.

So its time complexity is $O(j)$ and since the greatest value that $j$ takes is $m$, the time complexity of the algorithm is $O(m^2)$, right? (Thinking)

 

[alyafey22]

So its time complexity is $O(j)$ and since the greatest value that $j$ takes is $m$, the time complexity of the algorithm is $O(m^2)$, right? (Thinking)

Yeah , or you can write it more formally as

$$\sum_{j=0}^m(j-1) = \frac{m(m+1)}{2}-(m+1)\in O(m^2)$$

 

[evinda]

Yeah , or you can write it more formally as

$$\sum_{j=0}^m(j-1) = \frac{m(m+1)}{2}-(m+1)\in O(m^2)$$

Nice... Could we also say that the time complexity of the algorithm is equal to $$2c+\sum_{j=0}^m(j-1)=2c+\frac{m(m+1)}{2}-(m+1)\in O(m^2)$$
?In addition, I want to show that the following relation describes an invariant for the while-loop at the lines 3-5.

At the beginning of each iteration of the while-loop at the lines 3-5

$$k=\sum_{i=0}^{m-(j+1)} a_{i+j+1}x^i$$Is it right or is it a typo and it should be:

$$k=\sum_{i=0}^{m-(j+1)} a_{i+j}x^i$$

? (Thinking)

 

[alyafey22]

Nice... Could we also say that the time complexity of the algorithm is equal to $$2c+\sum_{j=0}^m(j-1)=2c+\frac{m(m+1)}{2}-(m+1)\in O(m^2)$$
?

In complexity analysis you have to choose an atomic operation that is you are interested in. For example, in sorting we are interested in element comparisons. What is the atomic operation in your question ?

In addition, I want to show that the following relation describes an invariant for the while-loop at the lines 3-5.

At the beginning of each iteration of the while-loop at the lines 3-5

$$k=\sum_{i=0}^{m-(j+1)} a_{i+j+1}x^i$$Is it right or is it a typo and it should be:

$$k=\sum_{i=0}^{m-(j+1)} a_{i+j}x^i$$

? (Thinking)

Sorry, I don't quite get the question ?

 

[evinda]

Sorry, I don't quite get the question ?

Which should be the coefficient of the sum? $a_{i+j+1}$ or $a_{i+j}$ ? (Thinking)

 

[alyafey22]

At the beginning of each iteration of the while-loop at the lines 3-5

$$k=\sum_{i=0}^{m-(j+1)} a_{i+j+1}x^i$$Is it right or is it a typo and it should be:

$$k=\sum_{i=0}^{m-(j+1)} a_{i+j}x^i$$

I don't see how any of representations could be true ?

 

[evinda]

Couldn't the function [m] pow(x,j) [/m] be implemented more efficiently?

 

[I like Serena]

Couldn't the function [m] pow(x,j) [/m] be implemented more efficiently?

The common implementation of the standard C/C++ [m]pow(x, y)[/m] function actually has constant time complexity.
Apparently it is typically implemented as $2^{y \log_2 x}$, and for $\log_2$ a lookup table is used, making it constant time.

 

[evinda]

The common implementation of the standard C/C++ [m]pow(x, y)[/m] function actually has constant time complexity.
Apparently it is typically implemented as $2^{y \log_2 x}$, and for $\log_2$ a lookup table is used, making it constant time.

Doesn't the following fuction has time complexity [m]O(exp)[/m] ?

int ipow(int base, int exp) { 
    int result = 1; 
    while (exp!=0) { 
             result*=base;
             exp-=1;
    } 
    return result; 
}

Is there a better algorithm?

 

[I like Serena]

Doesn't the following fuction has time complexity [m]O(exp)[/m] ?

Yes.

Is there a better algorithm?

Yes. (Nod)
For instance:

int ipow(int base, int exp) { 
    int result; 
    if (exp == 0) {
        return 1;
    }
    result = ipow(base, exp / 2);
    result *= result;
    if (exp % 2 == 1) {
        result *= base;
    }
    return result; 
}

It has complexity $O(\lg exp)$.

The complexity can be further improved by using look up tables. (Wasntme)

 

[evinda]

Yes. (Nod)
For instance:

int ipow(int base, int exp) { 
    int result; 
    if (exp == 0) {
        return 1;
    }
    result = ipow(base, exp / 2);
    result *= result;
    if (exp % 2 == 1) {
        result *= base;
    }
    return result; 
}

It has complexity $O(\lg exp)$.

Nice! And could we prove its correctness with the invariant that at each step it holds that [m] result [/m] is of the form $\text{ base }^{\lfloor \frac{j-1}{2}\rfloor }$, as follows? (Thinking)

• [m] Base Case [/m]: For $\text{exp}=0$, the algorithm returns $1$, so it is correct since result=$\text{ base }^{\lfloor \frac{\text{exp}}{2} \rfloor}=\text{base}^0=1$.
• [m] Induction Hypothesis [/m]: We suppose that $\forall 0 \leq j \leq \text{exp}: \text{result}=\text{base}^{\lfloor{ \frac{j}{2} \rfloor }}$
• [m]Induction Step[/m]: Suppose that the second argument of the algorithm is $\text{exp}+1$.
  Then $\text{result}=ipow(\text{base}, \lfloor \frac{\text{exp}+1}{2} \rfloor) \overset{\text{ Induction hypothesis}}{=} \text{base}^{\lfloor \frac{\text{exp}+1}{2} \rfloor}$

 

[I like Serena]

Nice! And could we prove its correctness with the invariant that at each step it holds that [m] result [/m] is of the form $\text{ base }^{\lfloor \frac{j-1}{2}\rfloor }$, as follows? (Thinking)

I don't understand.

In lines 6, 7, and 9 [m]result[/m] gets assigned a different value, so how can the invariant be true at each step. (Wondering)

 

[evinda]

I don't understand.

In lines 6, 7, and 9 [m]result[/m] gets assigned a different value, so how can the invariant be true at each step. (Wondering)

(Worried)

How else could we prove the correctness of the algorithm? (Thinking)

 

[I like Serena]

(Worried)

How else could we prove the correctness of the algorithm? (Thinking)

Proposition
[m]ipow(base, exp)[/m]$ = \text{ base }^{\text{exp}}$.

Proof by induction

• [m] Base Case [/m]: For $\text{exp}=0$, the algorithm returns $1$, so it is correct since $\text{ base }^{\text{exp}}=\text{base}^0=1$.
• [m] Induction Hypothesis [/m]: We suppose that $\forall 0 \leq j \leq \text{E}:$ [m]ipow(base, j)[/m] $= \text{ base }^{\text{j}}$
• [m]Induction Step[/m]: Suppose that the second argument of the algorithm is $\text{E}+1$.
  Then:
  

  int ipow(int base, int exp) {
                                     /* exp == E + 1 with E >= 0                             */
      int result; 
      if (exp == 0) {
          return 1;
      }
                                     /* exp / 2 <= E                                         */
      result = ipow(base, exp / 2);  /* result == base^⌊exp / 2⌋ (Induction Hypothesis)      */
      result *= result;              /* result == (base^⌊exp / 2⌋)^2                         */
      if (exp % 2 == 1) {
                                     /* result == (base^((exp - 1) / 2))^2 == base^(exp - 1) */
          result *= base;            /* result == base^exp                                   */
      } else {
                                     /* result == (base^(exp / 2))^2 == base^exp             */
      }
                                     /* result == base^exp                                   */
      return result; 
  }

  Thus [m]ipow(base, E+1)[/m]$ = \text{ base }^{\text{E}+1}$

(Nerd)

 

[evinda]

Proposition
[m]ipow(base, exp)[/m]$ = \text{ base }^{\text{exp}}$.

Proof by induction

• [m] Base Case [/m]: For $\text{exp}=0$, the algorithm returns $1$, so it is correct since $\text{ base }^{\text{exp}}=\text{base}^0=1$.
• [m] Induction Hypothesis [/m]: We suppose that $\forall 0 \leq j \leq \text{E}:$ [m]ipow(base, j)[/m] $= \text{ base }^{\text{j}}$
• [m]Induction Step[/m]: Suppose that the second argument of the algorithm is $\text{E}+1$.
  Then:
  

  int ipow(int base, int exp) {
                                     /* exp == E + 1 with E >= 0                             */
      int result; 
      if (exp == 0) {
          return 1;
      }
                                     /* exp / 2 <= E                                         */
      result = ipow(base, exp / 2);  /* result == base^⌊exp / 2⌋ (Induction Hypothesis)      */
      result *= result;              /* result == (base^⌊exp / 2⌋)^2                         */
      if (exp % 2 == 1) {
                                     /* result == (base^((exp - 1) / 2))^2 == base^(exp - 1) */
          result *= base;            /* result == base^exp                                   */
      } else {
                                     /* result == (base^(exp / 2))^2 == base^exp             */
      }
                                     /* result == base^exp                                   */
      return result; 
  }

  Thus [m]ipow(base, E+1)[/m]$ = \text{ base }^{\text{E}+1}$

(Nerd)

Great! (Happy)

I should write a pseudocode for the implementation of the simple algorithm of valuation of a polynomial that computes each term independently from the others. Also I have to find its time complexity and compare it with the corresponding time complexity for Horner's method.
So I could write the following pseudocode with the above function [m] pow [/m], right? (Thinking)

1.l<-0 
2.j<-m 
3.while j>=0{ 
4.       l+=pow(x,j)*a_j; 
5.        j-=1; 
6. }

Could we say the following?

We suppose that additions, multiplications and assignments take a constant time.
The while-loop is executed $m-1$ times.

The time complexity of the pseudocode [m] ipow [/m] is described by the recurrence relation $T(k)=T\left( \lfloor \frac{k}{2} \rfloor \right)+d$, where $d$ is a constant.

$a=1, b=2, f(n)=d$

$k^{\log_2 1}=k^0=1$

So, $f(k)=\Theta(k^{\log_b a})=\Theta(1)$, so from the second case of the Master Theorem, we conclude that $T(k)=\Theta(\lg k)$.

So the asymptotic time complexity of the pseudocode is $ \sum_{j=0}^m (c \lg j+e)=\sum_{j=0}^m c \lg j+ \sum_{j=0}^m e$, where $e,d$ constants.Or is it wrong? (Worried)
Because $\lg$ cannot take as an argument the value $0$...

 

[I like Serena]

Great! (Happy)

So the asymptotic time complexity of the pseudocode is $ \sum_{j=0}^m (c \lg j+e)=\sum_{j=0}^m c \lg j+ \sum_{j=0}^m e$, where $e,d$ constants.

Or is it wrong? (Worried)
Because $\lg$ cannot take as an argument the value $0$...

Looks good to me. :)
Except that you should indeed treat $j=0$ as a separate case.
It takes constant time to evaluate ipow(x,0), and not some negative number.

 

[evinda]

Looks good to me. :)
Except that you should indeed treat $j=0$ as a separate case.
It takes constant time to evaluate ipow(x,0), and not some negative number.

So is it right like that? (Thinking)

We suppose that additions, multiplications and assignments take a constant time.
The while-loop is executed $m-1$ times.

The time complexity of the pseudocode [m] ipow [/m] is described by the recurrence relation $T(k)=T\left( \lfloor \frac{k}{2} \rfloor \right)+d$, where $d$ is a constant.

$a=1, b=2, f(n)=d$

$k^{\log_2 1}=k^0=1$

So, $f(k)=\Theta(k^{\log_b a})=\Theta(1)$, so from the second case of the Master Theorem, we conclude that $T(k)=\Theta(\lg k)$.

So the asymptotic time complexity of the pseudocode is $ (cb+e)+\sum_{j=1}^m (c \lg j+e)=(cb+e)+\sum_{j=1}^m c \lg j+ \sum_{j=1}^m e \\ =(cb+e)+c \lg(m!)+e \frac{m(m+1)}{2} \in \Theta(m^2)$ where $e,d, b$ constants.

 

[I like Serena]

So is it right like that? (Thinking)

We suppose that additions, multiplications and assignments take a constant time.
The while-loop is executed $m-1$ times.

Isn't the while-loop executed $m+1$ times? (Wondering)

So the asymptotic time complexity of the pseudocode is $ (cb+e)+\sum_{j=1}^m (c \lg j+e)=(cb+e)+\sum_{j=1}^m c \lg j+ \sum_{j=1}^m e \\ =(cb+e)+c \lg(m!)+e \frac{m(m+1)}{2} \in \Theta(m^2)$
where $e,d, b$ constants.

I believe that should be:
$$(cb+e)+\sum_{j=1}^m c \lg j+ \sum_{j=1}^m e \\ =(cb+e)+c \lg(m!)+me \in \Theta(m\lg m)$$
(Wasntme)

 

[evinda]

Isn't the while-loop executed $m+1$ times? (Wondering)

Oh yes, you are right! (Wasntme)

I believe that should be:
$$(cb+e)+\sum_{j=1}^m c \lg j+ \sum_{j=1}^m e \\ =(cb+e)+c \lg(m!)+me \in \Theta(m\lg m)$$
(Wasntme)

(Nod)Now I have tried to prove that for the initial pseudocode that implements the Horner's method the following relation expresses an invariant for the while-loop at the lines 3-5.
At the beginning of each iteration of the while-loop at the lines 3-5$$k=\sum_{d=0}^{m-(j+1)} a_{d+j+1} x^{d}$$That's what I have tried:Initial check:
Before the first iteration of the loop, we have $j=m$ and $k=0$.
The sum $\sum_{d=0}^{m-(m+1)} a_{d+m+1} x^{d}=\sum_{d=0}^{-1} a_{d+m+1} x^{d}$ is zero, so it is equal to $y$, therefore the invariant holds before the first iteration of the loop.Maintenance:
We suppose that the invariant holds at the beginning of the iteration for $j=p$.
So $\sum_{d=0}^{m-(p+1)} a_{d+p+1} x^{d}$.
Then $k$ becomes:

$$a_p+x \cdot k=a_p+x \sum_{d=0}^{m-(p+1)} a_{d+p+1} x^{d}= \dots \dots= \sum_{w=0}^{m-((p-1)+1)} a_{w+(p-1)+1} x^w$$That means that the invariant continues to holds also before the next iteration, i.e. for $j=p-1$.Termination:

We want to check what happenswhen the loop ends.
The loop ends when [m] j [/m] becomes smaller than [m]0[/m], so when [m] j=-1 [/m].

In order to do this, do we set at the sum [m] j=-1 [/m], although the while-loop is never executed for [m] j=-1 [/m] ? (Thinking)

 

[evinda]

Also, I have to show that the given part of code valuates correctly a polynomial with coefficients $a_0, a_1, \dots, a_n$.

Could I say the following?

When the algorithm terminates, [m] j [/m] will have the value [m] -1 [/m], so from the invariant we have that [m] k [/m] is the value that we had to compute.