Find Top N : Solution 1

The problem is described here. Server-side Javascript in XPages in IBM Lotus Domino offers a function @Unique.

Let S strings be stored in an Array names. Passing this to @Unique returns uniqueNames. Let topNames stores the top N strings with highest occurrence count found so far in descending order of occurrence and topCount keeps track of respective occurrence count. Following is the rest of the algorithm.

For each string u in uniqueNames
Begin
   Initialize uniqueCount to 0
   For each string n in names
      if n matches u, increase uniqueCount
   For each count c in topCount
      if uniqueCount is greater than c
      Begin
         move all the elements in topNames and topCount back by one
         insert uniqueCount in topCount and u in topNames
      End
End

Since I don't have complexity numbers for @Unique, I take the worst case and assume it to be of . After that the above algorithm is executed which, if all the strings are unique, take time. So the time complexity of this algorithm is . In most of the practical scenarios, , so the time complexity can be assumed to be . Space complexity is .