Big O Notation

Question

Hi All,

I was asked how to code given this problem:

One Paragraph, get all unique words, and the number of times each unique words appeared. Apply Big O Notation.

Last time I checked, it was during college when I was first introduced to it and haven't used it ever since.

And what's the most efficient way of coding this problem?

Thank you very much.

Regards,
Jan

Alan · Answer

Well, we've got an Array.Sort which is O(n log n) on average and (ignoring the for loop which ouputs the results to the console) two for loops of O(n) each. So, overall, I'd say the algorithm will be O(n log n + 2n). Incidentally, it struck me later that I hadn't allowed for abbreviations such as e.g. or B.Sc.. It's quite tough to allow for them unless it can be assumed that when '.' is used to end a sentence it will always be followed by whitespace or will be the last character of the paragraph.

Jan Montano · Answer

Thanks Alan. I really need to study that Big O.

Jan Montano · Answer

Thanks Alan. Given that code, what is the Big O notation for it? Is it O(n * 3) ? I'm not quite sure. I just noticed that we have 3 loops.

Alan · Answer

Leaving aside questions of efficiency, the main problem here is dealing with punctuation and trying to decide what constitutes a 'word'. I've ignored capitalization and apostrophes but treated a hyphenated (or underscore separated) word as being a single word. I've also treated '&', surrounded by spaces, as a separate word and all numbers including embedded decimal points and thousand separators as being 'words'. In the belief that a conventional approach would probably be more efficient here than either regular expressions or LINQ, I've used the former. You'll see I've sorted the array of words to make it easier to count duplicates, though this might be less efficient than other approachs depending on the number of words in the paragraph. I've just assumed that the file contains a single paragraph rather than trying to parse out the first paragraph or anything like that: using System; using System.IO; using System.Collections.Generic; class Program { static void Main() { string text = File.ReadAllText("jan.txt"); // or whatever Console.Clear(); Console.WriteLine("The paragraph is :
"); Console.WriteLine(text); Console.WriteLine(); // convert everything to lower case text = text.ToLower(); char[] chars = text.ToCharArray(); // replace most non-alphanumeric characters with spaces for (int i = 0; i { if (!Char.IsLetterOrDigit(chars[i])) { if (chars[i] == ' ') // space { continue; } else if (chars[i] == '\'') // apostrophe { chars[i] = ' '; if (chars.Length - 1 > i && chars[i+1] == 's') { chars[i+1] = ' '; i++; } } else if (chars[i] == '-' || chars[i] == '_') // hyphen or underscore { if ((i > 0 && i { continue; } chars[i] = ' '; } else if (chars[i] == '&') //ampersand { if ((i > 0 && i { continue; } chars[i] = ' '; } else if (chars[i] == '.' || chars[i] == ',') // dot or comma { if ((i > 0 && i { continue; } chars[i] = ' '; } else { chars[i] = ' '; } } } text = new string (chars); // get all words string[] words = text.Split(new char[]{' '}, StringSplitOptions.RemoveEmptyEntries); // sort into alphabetic order so indentical words are adjacent to each other Array.Sort(words); // obtain list of unique words and their frequencies List uniqueWords = new List (); List wordCounts = new List (); uniqueWords.Add(words[0]); string currentWord = words[0]; int count = 1; for (int i = 1; i { if (currentWord == words[i]) { count++; } else { wordCounts.Add(count); uniqueWords.Add(words[i]); currentWord = words[i]; count = 1; } if (i == words.Length - 1) { wordCounts.Add(count); } } // display results Console.WriteLine("The word analysis is:
"); Console.WriteLine("Number of unique words : {0}
", uniqueWords.Count); for (int i = 0; i { Console.WriteLine("{0} : {1}", uniqueWords[i], wordCounts[i]); } Console.ReadKey(); } }

Big O Notation

Answers (4)