Entering edit mode

11.8 years ago

Snowball
▴
10

This error correction problem caught my eye. **Is there an O(n) algorithm for this**, where

*n*is the number of reads? There's the relatively straightforward

*O(n*method of checking all the pairs, but I'm wondering if there's something better out there.

^{2})
Forgive my ignorance, but I am not aware of the "O" term in the algorithm you mention, can you give us some more information on this method?

big O notation is just a way to describe how an algorithm performs given an input. You can read more about it here: http://en.wikipedia.org/wiki/Big_O_notation

For example, looking for an element in a dictionary/hash structure would be O(1) because you can directly access it in one operation. Whereas a primitive search algorithm where you iterate through an entire list of elements to find a specific element would be O(n) where n is the number of members in the list. A binary search tree where you effectively reduce your search space by 1/2 every node would give you O(logN) processes.

It's basically a way to describe the performance of an algorithm

+1 and thanks Damian! I come from a more strictly biological background so I need a little help with things sometimes.