CODEWITHSUNDEEP
rubyalgorithmtime-complexitybig-ospace-complexity
Henry
Henry

Reputation: 73

Time and space complexity of Ruby Anagram algorithm

I have written this algorithm here and I am trying to evaluate its time and space complexity in terms of Big-O notation. The algorithm determines if two given strings are anagrams. 

def anagram(str1, str2)
 str1.each_char do |char| 
   selected_index = str2.index(char)
   return false if !selected_index #to handle nil index

   str2.slice!(selected_index)
 end

 str2.empty?
end

The time complexity of this function is O(n^2), and the space complexity is O(1)? I believe I may be mistaken for the space complexity (could be O(n)) because the selected_index variable is repeatedly re-assigned which takes up memory relative to how long the each_char loop runs for.

If someone could please throw some guidance that would be great :)

Upvotes: 3

Views: 585

Answers (1)

joanis
joanis

Reputation: 12229

Gathering up all those comments into an answer, here is my analysis:

Time

The algorithm as presented does indeed have O(n^2) running time.

The body of the loop is executed n times and takes linear time for index, linear time for slice, and constant time for the rest, requiring a total of O(n^2) time.

Space

The algoithm as presented requires linear space, because it updates a copy of str2 at each iteration.

The rest of the algorithm only takes constant space, unless you include the storage for the inputs themselves, which is also linear.

Faster algorithm: sort str1 and str2

A faster algorithm would be to do string compare sort-by-character(str1) and sort-by-character(str2). That would take O(n log n) time and O(n) space for the sort; and linear time and constant space for the comparison, for an overall O(n log n) time and O(n) space.

Even faster algorithm: use a hash (proposed by OP in the comments)

Using hash tables to store character and then compare character counts can reduce the running time to O(n), assuming standard O(1) insert and lookup hash operations. The space in this case is the space required for the hash tables, which is O(k) for a character alphabet of size k, which can be considered constant if k is fixed. Of course, the input parameters still consume their initial O(n) space as they are passed in or where they are originally stored; the O(k) reflects only the additional space required to run this algorithm.

Upvotes: 2

Related Questions