1

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.

Community
  • 1
  • 1
user1339335
  • 451
  • 1
  • 4
  • 3
  • 2
    Please don't post the same question multiple times. – svick Apr 29 '12 at 12:02
  • Check this link, http://blogs.msdn.com/b/nmallick/archive/2010/03/30/how-to-calculate-time-complexity-for-a-given-algorithm.aspx?CommentPosted=true#commentmessage – Faizan Mar 03 '13 at 21:06

0 Answers0