Challenge for Running Time and Big-O

Challenge

Here's a simple algorithm (though non-optimal) to find a match of a substring word within a longer string text. It returns the index of the match, or -1 if no match is found.

Let n be the length of the text and m be the length of the word. What is the worst-case running-time of this algorithm?

static int indexOf(String text, String word) {
    for (int i = 0; i <= text.length() - word.length(); i++) {  // loop through text
        int j = 0;
        // loop through word
        while (text.charAt(i + j) == word.charAt(j)) {  //character match
            j++;
            if (j == word.length())
                return i;
        }
    }
    return -1;      
}

Please sign in or sign up to submit answers.

Alternatively, you can try out Learneroo before signing up.

Contact Us
Sign in or email us at [email protected]