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.