Editor">
Editor Staff asked 5 months ago
Editor Staff asked 5 months 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 5 months ago
Editor Staff answered 5 months 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).
