Path: utzoo!utgpu!news-server.csri.toronto.edu!mailrus!ames!decwrl!uunet!motcid!murphyn
From: murphyn@motcid.UUCP (Neal P. Murphy)
Newsgroups: comp.software-eng
Subject: Re: complexity question
Message-ID: <4358@bone13.UUCP>
Date: 3 Aug 90 13:50:08 GMT
References: <39400115@m.cs.uiuc.edu>
Organization: Motorola Inc., Cellular Infrastructure Div., Arlington Heights, IL
Lines: 30

marick@m.cs.uiuc.edu writes:


>I have a question related to program complexity vs size.  But, first,
>my terms:

>foo(a)
>{
>  if (global1 == global2)
>    global1 = a;
>}

>This has 4 data references but only 3 distinct references (since there
>are two duplicate references to global1).

>Now, if I had to guess, I'd guess that both the number of references
>and the number of distinct references grow linearly with program size
>(measured in lines of code or in number of tokens).  Does anyone know?

Well, if I may hazard a guess, I will say that you are correct, provided
your program is a simple filter or a simple pipe. But once you start
manipulating the data, the number of distinct references should fall
significantly behind the total number of references. And once you start
using the given data to create new data (lies, damn lies, statistics,
fitted curves and other such mathematical stuff), the total number of
references should grow even faster (arithmetically perhaps?).

Just a guess, though.

NPN