Beginning Java Data Structures and Algorithms

Complexity Notation

In the previous section, we have seen how we can use the big O notation to measure the runtime performance to our algorithms in proportion to the input size. We have neither examined in detail what O(n) really means nor have we considered the performance of our algorithm in relation to the type of input it's given.

Consider the following code snippet. The method accepts an array containing a string and searches for a match. If one is found, the index of the array is returned. We will use this example and try to measure the runtime complexity. The code is as follows:

public int search(String strToMatch, String[] strArray) {  for (int i = 0; i < strArray.length; i++) {    if (strArray[i].equals(strToMatch)) {      return i;    }  }