is there a faster way than O(n) to check if all elements in an unsorted array is 0?

Question

I have a code that needs to check if a given buffer of size 2048 is all zero. Right now I make a single traversal but wonder if there is a faster way to check if all contain 0. Is there a faster way? The cod e I have is as follows:

static int isSilent(Uint8* buf, int length){
       int i;
       for(i=0; i<length; i++)
          if(buf[i] != 0) return 0;
       return 1;
}

EDIT: I'm doing real time audio processing thus the small buffer size and trying to reduce the delay. Just trying to explore faster ways. Thanks.

I'm tempted to think along the lines of larger data sizes... — polarysekt, Sep 25 '14 at 00:00
2048 is a pretty small number. Presumably the array starts at all zeroes. Why don't you keep a flag for when you set the first non-zero value? But if you really must churn through a big array ... split it up into X ranges where X is the number of cores you have and run a few threads. — ta.speot.is, Sep 25 '14 at 00:00
If the buffer is sorted you can check the first and last elements... otherwise, I can't see an alternative that is not O(N). — vanza, Sep 25 '14 at 00:00

score 3 · Accepted Answer · answered Sep 25 '14 at 00:01

3

No, generally speaking if you want to check something about a whole array, you have to check the whole array. If you know something about the array in advance then of course you may be able to optimize this.

answered Sep 25 '14 at 00:01

Billy ONeal

104,103
58
317
552

score 2 · Answer 2 · edited May 23 '17 at 12:29

2

O(n) is the Big-O complexity for a linear scan.

Even if processing in a larger data-alignment (e.g. processing on word-or-larger boundaries), the constant time improvements are still factored out. Doing such optimizations/tricks¹, when applicable, may make for a better wall-clock time and "run faster" but don't affect the O(n) bounds.

However, make sure this is a relevant issue as 2048 elements is .. small, and the loop terminates as soon as a failing case is detected.

¹ There are various tricks that can be used in this case. One of the most notable examples is memcpy, shown in implementations such as this, which uses a "word aligned" loop.

edited May 23 '17 at 12:29

Community

1
1

answered Sep 25 '14 at 00:08

user2864740

60,010
15
145
220

1

In context, the `memcpy()` trick could mean checking single bytes until the pointer is aligned on a 4 byte (or even 8 byte) boundary; checking 4-byte (or 8-byte) units once it is aligned, and checking single bytes for any odd trailing bytes. This could achieve a significant speed-up. – Jonathan Leffler Sep 25 '14 at 00:36

Grzegorz Szpetkowski · Answer 3 · 2014-09-25T00:29:16.950

Theoretically speaking there is no such way. For unsorted array you must examine every element of it, so such operation has complexity of Θ(n). In practice you might utilize parallel processing using SIMD concept, but this seems to be an overkill for such simple (small?) task. Essentially the more processors you have, the greater speedup you can archieve. But assuming some k ∈ ℕ, where k > 0 is the number of processors you still have time complexity of Θ(n) for arbitrary large n.

is there a faster way than O(n) to check if all elements in an unsorted array is 0?

3 Answers3