Big-Oh notation theory, Exam perperation: Given This task, how can i calculate the big-Oh

Question

I am revising for my exams of sorting and algorithm analysis and one of the past exam papers has the following question:

"I would like to be able to take all the letters in some arbitrarily long word of N letters and nd the anagrams (real words that are made of the same letters e.g. DOG and GOD)."

My frst approach is this:
Find all the words by
Picking a first letter (N possibilities)
Picking a 2nd letter (N-1 possibilities)
Picking a 3rd letter (N-2 possibilities) etc.
For each word
Check it against a dictionary

What is the O(?) of this approach in relation to N the number of letters? Why?

My initial theory is that the process of picking a letter at random is going to be constant because it will take the same time to pick any letter so this would be O(1).

This applies to picking the 2nd and 3rd letters these will still take a constant time of O(1).

Now checking them against a dictionary will take O(1) as well, but this needs to be done for each word so it becomes O(n).

So my overall complexity would be O(n). I may have done something badly wrong here but i can see no nested loops so i can rule out O(n^2) and i cant seem to identity any elements that make it logarithmic so O(log n) is also ruled out.

Could somebody possibly provide an insight into this, and tell me where i have gone wrong.

Thanks, Chris.

Answer 1

From the question

"I would like to be able to take all the letters in some arbitrarily long word of N letters and nd the anagrams (real words that are made of the same letters e.g. DOG and GOD)."

you shall devise an algorithm to make all permutations of the input word alpha with arbitrary length n. The question suggests to take all letters, so only anagrams of length n are relevant for the answer.

If you use e.g. the QuickPerm algorithm, you have a time complexity of O(n!) I think.

Now you have to find out whether it is a real word. For this you use the given dictionary dict of all real words, which has a lookup complexity of O(1) and therefore has not to be considered.

So you have an overall complexity of O(n!).

Answer 2

Just wondering whether you could approach the algorithm slightly differently by searching the dictionary rather than all permutations of letter in the word

SO: Count each letter in the word and total word length (O=1, D=1, G=1) and word =3

for each word in the dictionary with length=3 Do the letter counts match exactly

Which I think is O(n^2)