Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!uwm.edu!ux1.cso.uiuc.edu!ux1.cso.uiuc.edu!m.cs.uiuc.edu!marick
From: marick@m.cs.uiuc.edu
Newsgroups: comp.software-eng
Subject: complexity question
Message-ID: <39400115@m.cs.uiuc.edu>
Date: 2 Aug 90 17:02:00 GMT
Lines: 25
Nf-ID: #N:m.cs.uiuc.edu:39400115:000:786
Nf-From: m.cs.uiuc.edu!marick    Aug  2 12:02:00 1990


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?
Number of distinct references is bounded below by the number of
variables in the program -- only a bound because of array references
-- so I'd be interested in figures on that, too.

Thanks.  I'm sure I've seen something like this somewhere.

Brian Marick
Motorola @ University of Illinois
marick@cs.uiuc.edu, uiucdcs!marick