CODEWITHSUNDEEP
performancealgorithmsorting
user2180833
user2180833

Reputation: 166

Is there a way to cut down my time complexity of O(n^2)?

I have made a program (hw), which count the frequency of all words. All of my algorithms takes O(n) or O(n log n), however my word counter takes O(n^2)

The algorithm looks like this:

for (int i = 0; i < no of elements; i++)
            for (int j = 0; j < no of elements; j++)
                if (the ith word == the jth word)
                {
                    increase that word counter by 1;
                    break;
                }

The reason i use this way is because the word list is unsorted. So my question is, would it be a good idea to use insertion sort or a sort which can sort the word list in alphebetical order? And how does such kind of sort look like for string array? The word list is a string array, eg:

string words[no of elements]

Thank you for your time.

Upvotes: 1

Views: 137

Answers (3)

Hynek -Pichi- Vychodil
Hynek -Pichi- Vychodil

Reputation: 26121

Make hash table for your words and then your word count will be O(n) because hast table look up will be O(1).

Upvotes: 2

Abhishek Bansal
Abhishek Bansal

Reputation: 12715

If you can make another data structure, then you can use map as well.

Just make a map<string, int> of word to count and update it as you iterate through the elements.

(Again O(nlogn) in time complexity)

Upvotes: 1

Abhishek Bansal
Abhishek Bansal

Reputation: 12715

Yes you can sort your elements in O(nlogn) time using any good sorting algorithm like quicksort. Then just check for repeats iterating over sequential elements.

EDIT: in most languages (like C++) the strings can be compared using normal comparison operators. and hence sorted like any array. Moreover, there are usually built-in functions to do so.

Upvotes: 1

Related Questions