What is the bestcase runtime for checking whether a trie con

What is the best-case runtime for checking whether a trie contains a particular string? Select all that apply.

a - O(n), where n is the number of nodes in the trie

b - O(n), where n is the number of strings that have been inserted into the trie

c - O(n), where n is the length of the string we\'re searching for

d - O(1), because it\'s possible for the trie to have just one node (the root node)

e - O(1), because the string we\'re searching for could have a single character

f - O(1), because the trie could be empty

g - O(1), because the string we\'re searching for could be the empty string (i.e., it has zero characters)

h - O(1), because the first letter in the string we\'re searching for might not be represented in the trie

i - O(1), because the string we\'re searching for might be the prefix of a much longer string (i.e., searching for \"be\" when the trie contains \"benevolent\")

Solution

The Best-case runtime for checking whether a trie conains any particular sting is as stated below -

The most suitable options would be -

as taken from the options stated in the question above -

a - O(n), where n is the number of nodes in the trie
c - O(n), where n is the length of the string we\'re searching for
d - O(1), because it\'s possible for the trie to have just one node (the root node)// make sure that it is initialized, else error would be thrown
e - O(1), because the string we\'re searching for could have a single character

// The root represents an empty string(\"\"), the vertexes that are direction of root repesent prefixes having the length1 1, also has the edges with distance 2 from the root with length prefix as 2, the verices has edges 3 from root. ie.any vertex, having \'x\' edge as adistance from root,will have an associated lenth for it
h - O(1), because the first letter in the string we\'re searching for might not be represented in the trie
i - O(1), because the string we\'re searching for might be the prefix of a much longer string (i.e., searching for \"be\" when the trie contains \"benevolent\")

// if std input, output is empty, then run time error would be thrown