2
$\begingroup$

I have an algorithm that:

1. takes in a book's text as a string.

2. splits that string into words and stores it in a list.

3. creates a hash table from this list by iterating over the elements of the list

4. It then iterates over a separate list of words to see if each of these words (in this separate list) is contained in the hashmap.

Three linear traversals occur here. One to split the input string into a word list, one linear traversal of the word list to create the hash table and one final traversal over the separate list to check each word is in the newly created hash table.

Time complexity is O(n + k + m), where n is the number of characters in the input string, k is the number of words and m is the number of words in the other list.

My question is, since k is derived from n and we can guarantee that k will always <= n can we omit n and write the complexity as O(n+m)?

$\endgroup$
1
$\begingroup$

Yes, you can. Since $k \le n$, you have $n+k+m \le 2n+m = O(n+m)$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.