# Tag Info

### Is there a complexity between $O(n)$ and $O(n \log n)$

$n \log\log n$ is between $n$ and $n \log n$, and is a relatively common one to find in the wild.
• 10.8k
Accepted

### Why are log and exp considered 'expensive' computations in ML?

To add to Lutz Lehmann's answer, you can look up the latency for the CPU instructions in this comprehensive table by Agner Fog. For example, on the Intel Ivy Bridge processors: FADD / FSUB (floating ...
• 8,142
Accepted

### Scientific Programming Contests

I don't know of any current contests, but you can definitely have a look at the SIAM 100-digit challenge. It's a set of 10 problems for which the contest required 10 correct digits per problem. All ...
• 6,066
Accepted

### Is the Thomas algorithm the fastest way to solve a symmetric diagonally dominant sparse tridiagonal linear system

I believe comparing an iterative method (multigrid) to a direct/exact method (Thomas) in terms of exact operation count isn't really meaningful. IIRC, Thomas operation count is $8N$ for any ...
• 2,203
Accepted

### Comparing Algorithmic complexity, ODE Solvers (Big O)

odeint from the SciPy library defaults to the lsoda integrator described here. However, any simple description of asymptotic ...
• 11.6k

### Is the Thomas algorithm the fastest way to solve a symmetric diagonally dominant sparse tridiagonal linear system

The short answer is that the Thomas algorithm will be faster than any iterative scheme for almost all cases. The exception would perhaps be applying a single iteration of a very simple iterative ...
• 4,521
Accepted

### How does the number of function calls in BFGS scale with the dimensionality of space?

That very much depends on your objective function. If you know that your objective function is highly multi-modal and complex, then BFGS is only going to give you a local minimum. If that is enough ...
• 226

### Why are log and exp considered 'expensive' computations in ML?

$\exp$, $\sin$, $\tan$ and their inverse and otherwise related functions are transcendental, defined by an infinite power series. Meaning it takes some effort to evaluate uniformly good approximations....
• 3,601

### Does the "cofactor technique" for inverting a matrix have any practical significance?

I'm going against the crowd - the adjugate matrix is in fact very useful for some specialty applications with small dimensionality (like four or less), in particular when you need the inverse of a ...
Accepted

### Computational cost of numerical methods for PDEs

I don't think is possible given that the nature of solutions to PDEs varies so much. However, a general heuristic you can have in your head is something like: Find out what type of equation (Eliptic, ...
• 11.6k