hi,
If the number of input data for my FFT block is N=m+k, m data are non zero
and k data are zero, how much is the order of computational complexity of
my FFT block? As you know if all inputs were non zero it will be
O(N/2*logN) but how about if I know that k of these N inputs are zero?
Regards

On Aug 16, 10:37=A0am, "ahmadagha23" <ahmadagha23@n_o_s_p_a_m.yahoo.com>
wrote:
> hi,
> If the number of input data for my FFT block is N=3Dm+k, m data are non z=
ero
> and k data are zero, how much is the order of computational complexity of
> my FFT block? As you know if all inputs were non zero it will be
> O(N/2*logN) but how about if I know that k of these N inputs are zero?
> Regards

i don't have my O&S handy at the moment.  i can't remember if there
are radix-2 forms (Decimation-in-Time or Frequency) that begin with
"little" butterflys (that use their neighboring bins) and do not bit-
reverse the data going in, but if there are such forms, you would be
able to write code that does not compute those butterflies (because
they just have zeros going in and will have zeros coming out).

but that code will be messy and i would bet the result would still be
O(N*logN).

also, the application of that (on the data, not an impulse response)
appears to be Overlap-Add, whereas i might suggest you try Overlap-
Save instead.  it's a little cheaper (you don't have to add the tails)
and there is no zero-padding of the data.

r b-j

robert bristow-johnson <rbj@audioimagination.com> wrote:
> On Aug 16, 10:37�am, "ahmadagha23" <ahmadagha23@n_o_s_p_a_m.yahoo.com>

>> If the number of input data for my FFT block is N=m+k, m data are non zero
>> and k data are zero, how much is the order of computational complexity of
>> my FFT block? As you know if all inputs were non zero it will be
>> O(N/2*logN) but how about if I know that k of these N inputs are zero?
>> Regards
 
> i don't have my O&S handy at the moment.  i can't remember if there
> are radix-2 forms (Decimation-in-Time or Frequency) that begin with
> "little" butterflys (that use their neighboring bins) and do not bit-
> reverse the data going in, but if there are such forms, you would be
> able to write code that does not compute those butterflies (because
> they just have zeros going in and will have zeros coming out).
 
> but that code will be messy and i would bet the result would still be
> O(N*logN).
 
With Big-Oh notation, the assumption is always for large (limit is
it goes to infinity) N.  Nice for doing the math, but not always
so useful in real problems.  Now, if k is fixed as m increases, such
that N goes to infinity then pretty obviously it is still O(NlogN).

If k is a constant fraction (approximately) of N, then maybe not.
Remember, though, that Big-Oh also ignores factors that don't
scale with N.  There are no algorithms O(2N), for example.

Even more interesting, you could make m=(N/2)+1.  Now it is
sort of obvious that O(NlogN) is also O(m log m).

-- glen