Beginning Java Data Structures and Algorithms

Linear Complexity

Linear algorithms are the ones where the work done varies in direct proportion with the input size, that is, if you double the input size, you double the work done. These typically involve a single pass through the input.

The problem presented in this example is that of counting the number of occurrences of a particular character in a string. Imagine we are given the string Sally sells sea shells on the seashore, and we want to find out the number of occurrences of the letter a.

The following code in Snippet 1.5 goes through each character in the input string and if the character at the current position matches the search letter, a counter is increased. At the end of the loop, the final count is returned. The code is as ...