Computational Complexity
n = |S|, m = |S
i
|
Each full level costs nm.
In the worst case there are O(n)
internal nodes.
So the worst case running time
is O(n
2
m)
In the best case there are O(logn)
full levels.
So the best case running
time is
Ω
(log(n)nm)
{S
0
, S
2
, S
3
}
{S
1
, S
4
}
Trivial Case
S
1
S
4
{S
0
, S
2
}
Trivial Case
S
0
S
2
S
3
{S
0
, S
1
, S
2
, S
3
, S
4
}