Re:Fast inverse chirp z-transform found
by labawi on Sunday October 13, 2019 @11:39AM
(#21240964)
The (log (log n)) factor in asymptotic complexity notation is almost meaningless.
* log₂ log₂ 2⁶⁴ = 6, which is essentially a constant factor if N<2⁶⁴
* to be fair, you may need to consider (log log N), or even (log log N)² factors hidden in native computer word size if exceeding N = 2⁶⁴.
* Today's machines have gone far from the classical computational complexity models, where data access patterns and locality matter orders of magnitude more than a factor which is essentially <= 6.
I would not immediately discard a (log log n) factor, but for nearly all purposes, I would mostly disregard it. So if the only difference were O(n·log n) vs O(n·log n·log log n), then no, it would not be a big deal.
* log₂ log₂ 2⁶⁴ = 6, which is essentially a constant factor if N<2⁶⁴
* to be fair, you may need to consider (log log N), or even (log log N)² factors hidden in native computer word size if exceeding N = 2⁶⁴.
* Today's machines have gone far from the classical computational complexity models, where data access patterns and locality matter orders of magnitude more than a factor which is essentially <= 6.
I would not immediately discard a (log log n) factor, but for nearly all purposes, I would mostly disregard it. So if the only difference were O(n·log n) vs O(n·log n·log log n), then no, it would not be a big deal.