+1 vote
in Data Structures & Algorithms I by (88.2k points)
For what size of nodes, the worst case of usage of space in suffix tree seen?

(a) n Nodes

(b) 2^n Nodes

(c) 2n nodes

(d) n! nodes

Question is taken from Suffix tree in division Trie of Data Structures & Algorithms I

The question was posed to me during an online exam.

1 Answer

+1 vote
by (672k points)
selected by
Best answer
Right choice is (c) 2n nodes

The best I can explain: In computer science, the worst case of usage of space in a suffix tree is found to be for a Fibonacci word for a full 2n nodes. The time complexity for usage of space is found to be O (n).

Related questions

Welcome to TalkJarvis QnA, a question-answer community website for the people by the people. On TalkJarvis QnA you can ask your doubts, curiosity, questions and whatever going in your mind either related to studies or others. Experts and people from different fields will answer.