CODEWITHSUNDEEP
javaalgorithmdata-structuresbig-otime-complexity
user2926514
user2926514

Reputation: 21

Running time of insertion into 2 hashtables with iteration and printing

I have a program that does the following:

Iterates through a string, placing words into a HashMap<String, Integer> where the key represents the unique word, and the value represents a running total occurrences (incremented each time the word is found).

I believe up to this point we are O(n) since each of the insertions is constant time.

Then, I iterate through the hashmap and insert the values into a new HashMap<Integer, List<String>>. The String goes into the List in the value where the count matches. I think that we are still at O(n) because the operations used on HashMaps and Lists are constant time.

Then, I iterate through the HashMap and print the Strings in each List.

Does anything in this program cause me to go above O(n) complexity?

Upvotes: 2

Views: 101

Answers (3)

Erik P.
Erik P.

Reputation: 1627

Beyond the two issues that Paul Draper and templatetypedef point out, there's another potential one. You write that your second map is a hashmap < int,list < string > >. This allows for a total linear complexity only if the implementation you choose for the list allows for (amortized) constant time appending. This is the case if you use an ArrayList and you add entries at the end, or you choose a LinkedList and add entries at either end.

I think this covers the default choices for most developers, so it's not really an obstacle.

Upvotes: 0

templatetypedef
templatetypedef

Reputation: 373082

You're correct, with a caveat. In a hash table, insertions and lookups take expected O(1) time each, so the expected runtime of your algorithm is O(n). If you have a bad hash function, there's a chance it will take longer than that, usually (for most reasonable hash table implementations) O(n2) in the worst-case.

Additionally, as @Paul Draper pointed out, this assumes that the computation of the hash code for each string takes time O(1) and that comparing the strings in the table takes time O(1). If you have strings whose lengths aren't bounded from above by some constant, it might take longer to compute the hash codes. In fact, a more accurate analysis would be that the runtime is O(n + L), where L is the total length of all the strings.

Hope this helps!

Upvotes: 1

Paul Draper
Paul Draper

Reputation: 83373

That is O(n), unless your word-parsing algorithm is not linear (but it should be).

Upvotes: 1

Related Questions