For what size of nodes, the worst case of usage of space in suffix tree seen?

Category: QuestionsFor what size of nodes, the worst case of usage of space in suffix tree seen?
Editor">Editor Staff asked 4 weeks ago

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 Answers
Editor">Editor Staff answered 4 weeks ago

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