Suppose a computer solves a coupled differential equations (with given boundary conditions) of which each equation deals with $2^n \times 2^n$ size of matrices as solutions. My question is

  1. Does time-scaling for typical algorithm we use in Python packages (e.g. Scipy) grow exponentially with $n$? This sounds pretty obvious to me, but I want make sure.
  1. Now we want to do matrix multiplications of $2^n \times 2^n$ matrices for fixed amounts of times. Does this task also take exponential time wrt $n$?

I'm not familiar with how general algorithms (in Python or other software) work to solve such two tasks. Intuitively, any calculation that deals with a matrix that grows exponentially wrt $n$ also seems to grow exponentially wrt $n$. Are there any counter examples for this task, except some tasks that only require us to look into specific region of the matrix (e.g. search time for the maximum diagonal elements of $2^n \times 2^n$ matrix would scale linearly with $n$)?

  • $\begingroup$ About 2: The output is exponential in $n$ (by definition), so any algorithm will have to work exponential amount of time (unless a succinct structure of a matrix is used and heavy assumptions are made on the input) $\endgroup$
    – nir shahar
    Commented Apr 4, 2022 at 0:19
  • 1
    $\begingroup$ I suspect asking what is the time complexity of "typical algorithm we use in Python packages" is likely to be viewed as off-topic here, and is too vague to answer in any case. Please ask only one question per post. $\endgroup$
    – D.W.
    Commented Apr 4, 2022 at 4:24


Your Answer

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