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$
    – Turbo
    Commented May 17, 2011 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$
    – Turbo
    Commented May 17, 2011 at 16:58


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.