I usually see books/references writing the complexity of such operations as $O(N \times \mathrm{log}_2(N))$; For example, the complexity of FFT/IFFT operation is $O(N \times \mathrm{log}_2(N))$. However, that operations requires approximately $5N \mathrm{log}_2(N)$ real operations (real additions + real multiplications). So I was wondering what is the complexity of big-$O$ in function of number of real operations? Can it be expressed by number of real operations?
1
-
$\begingroup$ "of such operations". Of what sort of operations? Or do you mean "of some operations"? Please edit your question for clarity. A citation would be helpful, too. $\endgroup$– TimWescottJul 19, 2022 at 19:02
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
1
Big O abstracts away knowledge about multiplies and adds and complex math, and focuses on how (whatever operations) scale when you increase N.
For the case of FFTs, the core operation that motivate the development of the algorithm may have been «multiplies» or «complex mult-add», but in real machines the bottle-neck often is more complex. Like cache layout, simd instructions or something else.
So we pick an algorithm that have been optimized for one set of resources, implement it on a machine with a different set of resources, then fiddle around until it executes fast enough.
-
1$\begingroup$ "then fiddle around until it executes fast enough" You forgot the "while pretending that we're doing pre-planned design". $\endgroup$ Jul 19, 2022 at 23:24
$\begingroup$
$\endgroup$
4
Look at any definition of big-O notation (i.e., the Wikipedia one).
$f(x)$ is said to be $\mathcal O\left(g(x)\right)$ if there is some finite number $A$ such that $|f(x)|$ is always less than $A g(x)$ as $x \to \infty$. Here, $g(x)$ is assumed to be strictly positive for all $x \geq x_0$.
$A$ does not have to be known for the above statement to be true -- it just has to be known to exist, and to be finite.
So, it's been proven for a long time, by people better at math than me, that the algorithmic complexity of the FFT is $\mathcal O \left(N \log N\right)$. But this still leaves room for clever people to come up with ways to reduce $A$.
Note that this seems to lead to trivial results -- but if you know the algorithmic complexity of something, you can get an immediate idea of how well it will scale. Something that's easy for five items but has an algorithmic complexity of $\mathcal O (N!)$ is probably not a good candidate for expanding out to 5000 items. On the other hand, something that's moderately hard for five items but has an algorithmic complexity of $\mathcal O (\log N)$ is going to be a slam dunk* to expand to 5000 items.
* I doubt any real algorithm is that easy -- I'm purposely choosing an absurd lower extreme.
answered Jul 19, 2022 at 19:13
-
$\begingroup$ No,Tim, what Wikipedia says is not quite what you claim it says. $f(x)$ doesn't converge to $Ag(x)$ as $x \to \infty$, but rather that there is an $x_0$ such that for all $x > x_0$, $|f(x)| \leq Ag(x)$ where $g(x)$ is a strictly positive function for all large values of $x$. For example, $x^3+x^2+x+1 = O(x^3)$ even though $f(x)$ does not converge to $Ax^3$ even for $A=1$; the difference between $x^3+x^2+x+1$ and $Ax^3$ increases without bound as $x \to \infty$. -1 pending corrections. $\endgroup$ Jul 20, 2022 at 3:23
-
$\begingroup$ I quite like your $\mathcal O(N!)$ nightmare example! For example, a decoding algorithm that would need to try all permutations of a received sequence of length $N$ (e.g. because these were words sent through a reordering network) would have to do (exactly, but also) $\mathcal O(N!)$ tests , whereas if the sequence could be correctly ordered by some property, that complexity would reduce to (e.g. through heapsort) to an $\mathcal O (N \log N)$. $\endgroup$ Jul 20, 2022 at 7:50
-
$\begingroup$ @DilipSarwate: Thank you. I've corrected my text (hopefully). I knew that. Really, honest, I did! That part of my brain must just have been asleep. $\endgroup$ Jul 20, 2022 at 14:10
-
1$\begingroup$ OK, I have corrected your update a little and removed my downvote. As to the rest of your post, the issue is that $O$-notation only tells you of the asymptotic behavior, not the behavior for smaller $x$. For example, when $N=16$, $5N\log_2N$ equals $320$ while $N^2$ is $256$. $\endgroup$ Jul 20, 2022 at 15:50
$\begingroup$
$\endgroup$
3
That's literally the point of big-O notation: you can't tell that. All you can give is an upper bound of the growth.
answered Jul 19, 2022 at 11:58
-
$\begingroup$ Hi! There's been a downvote. That's very fine! I might be wrong, or the answer might be badly worded. I thought it was correct and on-point, so if the downvoter could come back and comment what's wrong about the answer, I'd love to improve it :) $\endgroup$ Jul 19, 2022 at 15:58
-
$\begingroup$ I didn't downvote your answer but it is indeed badly worded and misleading. $\endgroup$ Jul 20, 2022 at 3:09
-
$\begingroup$ @DilipSarwate hey, thanks for the feedback :) $\endgroup$ Jul 20, 2022 at 7:42