This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 2.5 License.
In order to make things a bit more interesting, the code actually finds all instances of a search term in a given list. For this slightly extended task, most of the code samples are pretty efficient as they effectively just walk through the list and note all of the occurrences of the search term. That is, for a list of n-items, such code has a time complexity of O(n). However, this is not true for all of the code samples. For instance, the Java code given here is fairy inefficient, as it repeatedly: (a) performs a linear search starting at the beginning of the list; (b) if it finds a match, the entry is removed from the list before performing step (a) again in order to search for additional matches. While always starting the search from the beginning of the list in step (a) is clearly wasteful, step (b) is also fairly costly. This is due to the list being stored as an ArrayList, and thus every time an item is removed, the remaining items that followed the deleted one in the list must each be shifted over 1 position in order to fill the newly created gap. Moreover, both step (a), with its restarting of the search at the beginning of the list, and step (b), with its shifting of the contents of the array, are sufficient, even in isolation, to increase the time complexity required to find m matching terms in a list of n-item to O(n*m). Since m could, in principle, equal the length of the list, that is every entry in the list could be the search term that we're looking for, the time complexity can be given as O(n2).
Miscellaneous notes: Most of the code supports searching through lists of arbitrary strings. However, the Octave code only allows for lists of floating point numbers. Also, the C implementation is limited to lists containing strings no longer than 1024 characters.
![[Valid RSS]](/renma/images/valid-rss.png "Validate my RSS feed")
