What is the best-case runtime for checking whether a trie contains a particular

Question

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")

Explanation / Answer

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

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.