ashwin@uicsl.UUCP (04/24/84)
#N:uicsl:17400001:000:3473
uicsl!ashwin Apr 24 14:33:00 1984
**munch**
Sanjai's program for breadth-first traversal of a tree actually is of
O(v squared) time complexity, not O(v) as claimed. The problem, of course,
is that the top-level abstract algorithm bf is indeed O(v), but the succ
predicate is an O(v) linear search through v clauses, the search being
performed once for each of the v vertices in the tree; hence O(v squared).
This is a problem not with the algorithm, but with its implementation in the
given language (Prolog), or more precisely, with the serial search
methodology that is the basic control mechanism employed in Prolog.
For those who are not convinced, here's an outline of the complexity argument
for the given program.
level tree
0 O root Consider a complete binary tree with all
/ \ its leaves at level L (numbered 0 to L so
1 O O that the height h of the tree is L)
/ \ / \
L=2 O O O O leaves Number of nodes or vertices v = 2^(L+1) - 1
At level l, there are 2^l nodes. Also, L+1 = lg(v+1).
The top-level clause
bf([],[]).
bf(L,Z):-successor_list(L,SL),bf(SL,BSL),append(L,BSL,Z).
is recursively called L+1 times, once for each level. On the call for the
level l (l=0,..,L), successor_list and append are called with their
respective first arguments being a list of length 2^l (which is the number of
nodes on that level). The successor_list call is O(v times 2^l) (see below),
and the append call is O(2^l) (The append clause is of the order of the
length of its first argument). The bf algorithm is therefore of the order of
L or lg(v+1)-1
__
\
/ (v 2^l) = O(v^2) (that's "order of v squared")
--
l=0
Successor_list recurses n times, where n is the length of its first argument.
successor_list([],[]).
successor_list([U|V],Z) :-
succ(U,SU), successor_list(V,SV), append(SU,SV,Z).
Each time, it calls succ (which is an O(v) linear search through all the
succ(Node,List_of_successors) clauses), and also append (which is O(2) or
constant time since its first argument is of length 2 (remember we have a
binary tree)). Therefore successor_list has a time complexity of O(vn).
When called from bf with a 2^l long list (on the 'l'th level), it is
of O(v 2^l) time.
Ashwin Ram
University of Illinois at Urbana-Champaign
...uiucdcs!uicsl!ashwin
------------------------------------------------------------------------------
The original note:
>> The following pure Prolog program will do breadth-first
>> traversal of a tree in o(v) time. The input to 'bf' is
>> a list of nodes at some level. (At the top level it is
>> simply [root]). The output is a list of nodes of the
>> tree traversed in breadth-first order.
>>
>> The algorithm may also be used to traverse a graph without
>> cycles, but as there is no equivalent of a 'mark' bit here,
>> nodes may be repeated in the output.
>>
>> bf([],[]).
>> bf(L,Z):-successor_list(L,SL),bf(SL,BSL),append(L,BSL,Z).
>>
>> successor_list([],[]).
>> successor_list([U|V],Z):-succ(U,SU),successor_list(V,SV), append(SU,SV,Z).
>>
>> append([],X,X).
>> append([U|V],W,[U|Z]):-append(V,W,Z).
>>
>> Procedure 'succ' contains clauses of the form
>>
>> succ(Node,Successor_list)
>>
>> where 'Successor_list' is a list of immediate sucessors of
>> 'Node'. If 'Node' is a terminal node then 'Successor_list'
>> is [].
>>
>> -- Sanjai Narainpereira@sri-unix.UUCP (05/02/84)
Your criticism of Sanjai's article is not quite correct. It is true that in most Prolog systems the complexity would be O(n^2) because of the clause search for succ, but this not necessarily so. On DEC-10/20 Prolog, for example, clauses are indexed on their first argument and so the succ lookup would be O(1). I think that some other Prolog systems (LM-Prolog comes to mind) have similar facilities. -- Fernando Pereira