This is a simple worst-case complexity problem, but I\'m having trouble grasping

Question

This is a simple worst-case complexity problem, but I'm having trouble grasping the concept.

The following code counts how often different words occur in a text file.

Let W denote the number of words in being processed.
Many of these words, in a typical document, will be duplicates. Let D denote the number of distinct (non-duplicate) words, D <= W.
Assume the length of any individual word is bounded by some constant (e.g., no single word is longer than "antidisestablishmentarianism").

What is the worst-case complexity for countWordsInFile?

Explanation / Answer

char toLC (char c) { return (c >= 'A' && c Runs for O(1) time } void countWordsInFile (istream& inFile, map& counts) { string word; while (inFile >> word) ==> Runs for O(W) time { // strip away any non-alphabetic characters string::size_type n = word.find_first_not_of (wordCharacters); ==>O(length of Word) if (n != string::npos) => ==>O(length of Word) word = word.substr (0, n); ==>O(length of Word) if (word.length() > 0) => O(1) { // if there's anything left, count it word = transform(word.begin(), word.end(), word.begin(), toLC); ==>=>O(length of Word) /** ... increment the appropriate counter in counts ... **/ map::iterator pos = counts.find (word); => O(log W) time to find if (pos == counts.end()) // if this is the 1st time we've seen // this word counts.insert (map::value_type(word, 1)); else // else if we've seen this word before ++((*pos).second); } } } Hence the Total time complexity is (W*length of word) + (W*log(W)) =>Since length of word is constant The Complexity is O(W*log(W)

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.