I am trying to understand how word sizes in a problem affects complexity. The question could be a simple technicality I am trying to clarify since I am not from mainstream CS. Let $V$ be an $n \times n$ fixed Vandermonde matrix and $A$ an $n \times 1$ arbitrary vector. Both $V$ and $ A$ have entries in $\mathbb{Z}$. Both $VA$ and $V^{T}A$ can be calculated in $O(n\log^{a}n)$ multiplications and additions on a fixed word machine ($a$ is a positive constant).


Does the above complexity result hold when $V$ is generated by a number of size $O(\log^{b}{n})$ bits where $b$ is a positive constant? In this case, the highest number in $V$ is of size $O(n\log^{b}{n})$ bits. Shouldn't this have an impact?

  • $\begingroup$ I am beginning to see your point. $\endgroup$ – 1.. May 17 '11 at 13:50
  • $\begingroup$ The reason I am asking is due to a related problem, given the $n^{th}$ column of $V$ which are powers of $X^{n-1}$ where $X$ generates $V$ and a matrix $B$ whose entries are of size $O(\log n)$, it seems impossible to find the vector $BV$ in $O(n\log^{b}(n))$ complexity since $V$ has words of size $O(n\log^{b}(n))$ and one has to multiply $n^2$ elements of $B$ with individual elements of $V$. Is my reasoning on bit complexity wellfounded in this case? $\endgroup$ – 1.. May 17 '11 at 16:58

Your Answer

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

Browse other questions tagged or ask your own question.