What is the complexity of creating a lexicographic tree

+1 A:

The appropriate data structure for this is probably a sorted list. In that case this becomes a bisection search problem, so O(log n).

cletus 2009-10-17 03:12:31

+1 Since you are given a sorted list up front, this is probably correct (i.e. the answer his professor is looking for :-)

Gabe Moothart 2009-10-17 03:25:06

A:

just run with a simple loop and check whether each word start with whatever.

in almost every language there is a build in function for check whether one string start with another.

the complexity is O(log n), while n being the number of the words in the dictionary.

Itay 2009-10-17 03:15:17

A simple loop would be O(n).

Greg Hewgill 2009-10-17 03:22:38

but you stop as soon as you find

Itay 2009-10-17 15:22:33

Which means you'll have to scan, on average, half the list, which makes it O(0.5n), which is O(n).

Nick Johnson 2009-10-19 08:38:36

+2 A:

If you create a prefix tree out of your input, you can perform this query in constant time.

Edit

The query is linear in the length of the search string. I meant that it was constant with regard to the size of the word list.

Gabe Moothart 2009-10-17 03:16:29

A:

giolekva 2009-10-17 05:56:23

It's not O(n log n) to find a single word in a dictionary using binary search! It's O(log n).

Nick Johnson 2009-10-17 11:10:29

ansaurus