Big(O) question for a simple recursive backtracking example
entangled
61

finding it hard to wrap my head around the big O for a simple backtracking using recursion..
the time complexity seems like n! (n is number of words that start at remaining string); how do we represet big O when the time depends on more than one input

is my reasoning correct?

//canFormWord("dawhaty", []string{"a", "what", "an", "nice", "day"}) returns false
//canFormWord("whataniceday", []string{"a", "what", "an", "nice", "day"}) returns true
func canFormLeftOverWord(s string, words []string) bool {
	if len(s) == 0 {return true}
	for i := range words{
		if len(s) >= len(words[i]) && s[0:len(words[i])] == words[i] && canFormLeftOverWord(s[len(words[i]):], words){
			return true
		}
	}
	return false
}
Comments (0)