Order of growth definition from Reynolds & Tymann

Question Detail: 

I am reading a book called Principles of Computer Science (2008), by Carl Reynolds and Paul Tymann (published by Schaum's Outlines).

The second chapter introduces algorithms with an example of a sequential search which simply iterates through a list of names and returns TRUE if a given name is found in the list.

The author goes on to say (page 17):

We say that the "order of growth" of the sequential search algorithm is n. The notation for this is T(n). We also say that an algorithm whose order of growth is within some constant factor of T(n) has a theta of NL say. "The sequential search has a theta of n." The size of the problem is n, the length of the list being searched.

I find this really hard to follow. The book is riddled with errors, so I am not sure if I am missing something or if the there is a typo in the paragraph above. In general English I rarely see any sentence end with "...say".

I am very confused.

What does T stand for? The book does not explain. Is it for Time or for Theta?

If "a theta of NL" means "The sequential search has a theta of n." What does L stand for? 'Linear' or 'length'?

I have written to the publishers asking for an explanation. They said they would forward my message to authors. They have not replied. I have also tried looking at other sources but I still get the naggling feeling that I am misunderstanding something - so cannot rest until I have decoded this paragraph.

If anyone has a copy of that book, and has understood that paragraph. Then, I'd appreciate if you could let me know if that paragraph is accurate or explain it in other words. Thanks.

Asked By : JW.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/50993

Answered By : David Richerby

The paragraph is wrong. Unfortunately, it looks exactly like the kind of thing that a student who does not understand the material would write as an answer to an exercise. This sort of nonsense has no place in a textbook. Make no sudden movements. Put the book down. Step away from the book.

We say that the "order of growth" of the sequential search algorithm is n. The notation for this is $T(n)$.

No. $T(n)$ is the notation for a function called $T$, which takes an argument called $n$. That function could be used to mean anything whatsoever. There is something of a tradition of writing recurrence relations for the running time of programs in the form, e.g., $$\begin{align*} T(1)&=k\\ T(n)&=T(n-1)+\log n \quad\text{for }n>1 \end{align*}$$ But $T$ is not an "order of growth", here: it is a specific function defined through a recurrence relation. And you cannot just write "$T(n)=\text{blah}$" and expect people to read your mind and know that the function $T$ denotes the running time of some algorithm. $T$ here stands for time.

We also say that an algorithm whose order of growth is within some constant factor of $T(n)$ has a theta of NL say. "The sequential search has a theta of $n$."

This has obviously been mangled. I think the authors intended to write something like,

We also say that an algorithm whose order of growth is within some constant factor of $T(n)$ has a theta of $\boldsymbol{n}$ and we say, "The sequential search has a theta of $n$."

But, please, we do not say "has a theta of $n$," just as, if $h$ is your notation for height, you wouldn't say "John has an $h$ of 180cm." It's just not a correct form of words. We actually say, "The running time of the algorithm is theta $n$ (or theta of $n$)." Note in particular, that $\Theta$ is a tool for talking about mathematical functions, not algorithms. Theta doesn't mean that the running time is something; rather, it's something you can use to talk about the running time.

"NL", by the way, denotes the complexity class nondeterministic logspace, which makes no sense at all in the position it appeared in the original quote.