Time Complexity for an algorithm

Question

Am I correct in my explanation when calculating the time complexity of the following algorithm?

A HashSet, moduleMarksheetFiles, is being used to add the files that contain the moduleName specified.

for (File file: marksheetFiles){ while(csvReader.readRecord()){ String moduleName = csvReader.get(ModuleName); if (moduleName.equals(module)){ moduleMarksheetFiles.add(file); } } }

Let m be the number of files
Let k be the average number of records per file.
As each file is added only once because HashSet does not allow for duplicates. HashSet.add() is O(1) on average and O(n) for worst case.
Searching for a record with the specified moduleName involves comparing every record in the file to the moduleName, will take O(n) steps.

Therefore, the average time complexity would be: O((m*k)^2).

Is this correct?

Also, how would you calculate the worst case?

Thanks.

PS. It is not homework, just analysing my system's algorithm to evaluate performance.

In your 4th and 5th bullets, is n == m? Also, once you add file to moduleMarksheetFiles, why not break out of the inner loop? Finally, what kind of data structure is marksheetFiles? — Ted Hopp
– Ted Hopp, Commented Apr 29, 2012 at 1:53
@Ted Hopp -marksheetFiles is also a HashSet data structure. Yes n==m in the 5th bullet point sorry. As the system is already developed, it is not possible to add the break currently until the next cycle. Thanks for the advice though — user1339335
– user1339335, Commented Apr 29, 2012 at 2:05
@Kevin - I thought its squared because you would have to compare every record to the moduleName. Is the incorrect. Could you explain as to why you think its O(mk)? — user1339335
– user1339335, Commented Apr 29, 2012 at 2:09
unless moduleName.equals(module) takes O(mk) time, the overall time complexity is O(mk). — deebee
– deebee, Commented Apr 29, 2012 at 3:35

Thomas · Accepted Answer · 2012-04-30 18:09:19Z

No, it's not squared, this is O(nk). (Technically, that means it's also O((nk)²), but we don't care.)

Your misconception is that it the worst-case performance of HashSet is what counts here. However, even though a hashtable may have worst-case O(n) insertion time (if it needs to rehash every element), its amortized insertion time is O(1) (assuming your hash function is well behaved; File.GetHashCode presumably is). In other words, if you insert multiple things, so many of them will be O(1) that the occasional O(n) insertion does not matter.

Therefore, we can treat insertions as constant-time operations, so performance is purely dictated by the number of iterations through the inner loop body, which is O(nk).

Linear in the product of the number of files and the average number of lines per file, yes. Or, in other words, linear in the total number of lines across all files.
Your last statement is misleading. HashSet insert is O(nk) worst case, even with infinite size table, which doesn't need rehashing - due to collisions. assume hash(element)=1 [for each element] - every search is O(n), thus worst case complexity of the entire algorithm is indeed O(n^2k^2). Average case is of course not.
Right, yes, I'm assuming a well-behaved hash function. File, being from the standard library, presumably has one.
As I said it is misleading - not wrong. The intent is clear for experienced readers - but might confuse novice programmers.

Collectives™ on Stack Overflow

Time Complexity for an algorithm

1 Answer 1

5 Comments

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

5 Comments

Linked

Related