Path: csiph.com!usenet.pasdenom.info!weretis.net!feeder4.news.weretis.net!eternal-september.org!feeder.eternal-september.org!mx02.eternal-september.org!.POSTED!not-for-mail From: Ben Bacarisse Newsgroups: comp.programming Subject: Re: Some observations about "data structure complexity" Date: Tue, 28 Jul 2015 00:53:00 +0100 Organization: A noiseless patient Spider Lines: 14 Message-ID: <87vbd5xin7.fsf@bsb.me.uk> References: Mime-Version: 1.0 Content-Type: text/plain Injection-Info: mx02.eternal-september.org; posting-host="017616aa25f81ec581c44d76d61ba2f3"; logging-data="24607"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX19dKbMmfsap7U4ccT9+l5pd8hIrY522B0E=" Cancel-Lock: sha1:i7jG90a4IcOesggOjYNvp322i4U= sha1:qRzYwdqQcMgh3jljMJK2/soqSu4= X-BSB-Auth: 1.ae2cc4bba66913ed1059.20150728005300BST.87vbd5xin7.fsf@bsb.me.uk Xref: csiph.com comp.programming:5525 joshipura@gmail.com writes: > Question 3. Is this what we mean when we say "data structure A is more > complex than data structure B"? If there is a subset of instances of A that are isomorphic to all the instances of B, then it is reasonable to say that A is more complex than B. This is not a full answer (there many be other factors that people consider important to "complexity") but it does answer your initial question about why trees are considered more complex that lists: a subset of trees is isomorphic to the set of lists. -- Ben.