Possible Duplicate:
Time Complexity for an algorithm
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. -marksheetFiles is a Hashset. -if module is 'Maths' then any mark sheets with module 'Maths' gets added to the HashSet.
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.