Time complexity of sum of $2^n$ values of polynomials

Question

First a simpler question: let $q_{1}(k),\dots,q_{n}(k)$ be $n$ polynomials of degree smaller or equal to $n$.

Let $f(n): \mathbb{N} \rightarrow \mathbb{N}$ defined by $f(n) = \sum_{i=1}^{n}q_{i}(n)$.

Assume also $0\leq f_{i}(n)\leq n$.

What is the time complexity as a function of the input size for calculating $f(n)$ by the above definition?

I'm not quite sure how to approach this, but my current guess is as follows:

I know evaluating a polynomial is $O(n)$ time, where $n$ is the degree of the polynomial.

I know adding two integers is $O(n)$ where $n$ is the number of bits of the larger integer.

Every try to calculate this seems to get stuck, as i'm getting confused between the time complexity by input size and by actual size (the number itself).

after understanding this, i would like to understand the calculation for time complexity as a function of the input size for a similar problem:

Let $q_{1}(k),\dots,q_{2^n}(k)$ be $2^n$ polynomials of degree smaller or equal to $2^n$.

Let $f(n): \mathbb{N} \rightarrow \mathbb{N}$ defined by $f(n) = \sum_{i=1}^{2^n}q_{i}(n)$.

Assume also $0\leq f_{i}(n)\leq 2^n$.

Thanks for any help, i hope this is well enough defined.

Answer 1

It takes $O(n^2)$ time. A polynomial can be represented as the list of its coefficients. Since it has degree $n$, it can be represented by a list of $n+1$ numbers. Now adding polynomials can be done by adding their corresponding coefficients. There are $n+1$ coefficients of $f(n)$, and each takes $O(n)$ time to compute (you have to add up $n$ numbers), for a total of $O(n \times (n+1)) = O(n^2)$.

There's no possibility to do anything faster, as the input contains $n(n+1)$ numbers, and any correct solution will have to read all the input. It takes $\Theta(n^2)$ time even to read the input, let alone to do any processing, so any correct algorithm will have to take time at least $\Theta(n^2)$.

With this, you should now be able to do a similar analysis for the variant you list near the end of your question.