Tag Info

New answers tagged


To determine the complexity class of an algorithm, you have to determine which operation can be done in unit time. For example, a typical PC will to word-size, $w$-bit (32- or 64-bit) addition and multiplication in constant time. From that, you can calculate how many of those primitive operations an algorithm requires. To multiply two $2w$-bit numbers using ...


The names of complexities normally refer to $b$, not the bitlength $n$. $\mathcal{O}(log\ n) = \mathcal{O}(b)$ is polynomial time, $\mathcal{O}(n) = \mathcal{O}(2^b)$ is exponential time. Matrix multiplication of a matrix of length $n$ would involve more operations than multiplying all elements of your group with all others. It has complexity of ...

Top 50 recent answers are included