performance - Runtime of string concatenation checking algorithm -

i wrote algorithm check whether or not string concatenation of number of strings in array (while being able use string multiple times). i'm having trouble figuring out runtime of algorithm is.

i check string in question against every word in array , when find word substring of original string starting @ index 0, check remaining substring against every word in array well. i'm thinking o(n^n), unless i'm missing something.

def check_concat(str,substr,words)   if substr == ""     return false   end    words.each |word|     if word == substr && str != substr       return true     end     if substr.index(word) == 0       if check_concat(str,substr[word.length..-1],words)         return true       end     end   end   return false end 

let assume main string contains m words , there n words in array searched. in worst case need check each word in main string each word in array, mn time. time complexity of function o(mn).

for example main string "hello hello hello hello hello". array checked contains following words 'hai', 'fine', 'hello'. function require total of 15 comparisons.