New answers tagged efficiency
0
Here is an attempt.
The Fourier transform decomposes a signal into superimposed sine waves of various frequencies (this can be demonstrated visually).
It turns out that we can find out the strength of a specific wave in a specific signal by multiplying the signal with the wave and summing the resulting signal (again, this can be demonstrated visually).
The ...
2
What does a Fourier transformation do? It takes a sequence of values, like the sound volume recorded on a CD with 44,100 values per second, and transforms it into frequencies. That is very useful for example for compression, because frequencies change much less than volumes. Or it can be used to remove noise, because when you look at frequencies, noise is ...
0
EDIT: Indeed my previous answer was misleading, since I stated that recursive summation like in merge sort saves calculations and that is of course not true.
What does happen here however is that instead of doing 2N operations on each of the N vectors members (multiplication and summation), we do 2*lg(N) operations, which are caused thanks to recycling of 2 ...
0
For 1) Use any $O(n \log n)$-time sorting algorithm, like Mergesort. Without additional assumptions on the elements you cannot do better.
For 2) Use Radix sort with any base $b = n^\epsilon$ for any constant $\epsilon \in (0, 1]$ of your choice. For example pick $\epsilon =1$ so that $b=n$. The time needed for each iteration of Radix sort will be $O(n+b) = ...
Top 50 recent answers are included
