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.