4 ms·
If the input maxes out at 64 bits, then calculating the Fourier transform is O(64), which is O(1).
by beervirus 6y ago
If the input maxes out at 64 bits, then calculating the Fourier transform is O(64), which is O(1).
- adamnemecek 6y agoI don't follow.
- beervirus 6y agoO(whatever) refers to the asymptotic behavior as n gets arbitrarily large. If n is bounded, big O notation doesn’t really mean anything because everything is O(1).
- adamnemecek 6y agoI understand big O however Fourier bio O runtime is bound by the length of the signal, not by maximum value of the signal.
- hansvm 6y agoThe photonic processor in question can only process some maximum M number of bits worth of signal in a given time T though. To have a throughput of better than M/T you need more time or more/better processors (i.e., for large enough inputs the runtime isn't actually O(1) ). What I was pointing out is that digital implementations have this exact same property -- if the input is bounded in the sense that there are a maximum number of bits being fed into your digital computer then the maximum runtime is a constant equal to the maximum runtime for any of those finite inputs -- i.e., the runtime is O(1) for the inputs you're actually able to provide (the exact same inputs you could provide to the photonic processor to achieve a constant-time Fourier transform). To scale up beyond that threshold you still need more time or more/better processors.
- adamnemecek 6y agoAre we talking about analog computers?
- FeepingCreature 6y agoYes.