47
$\begingroup$

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.

Improve this question
$\endgroup$
3
  • $\begingroup$ Time complexity T(n), from Wikipedia: " Since an algorithm's performance time may vary with different inputs of the same size, one commonly uses the worst-case time complexity of an algorithm, denoted as T(n), which is defined as the maximum amount of time taken on any input of size n. Less common, and usually specified explicitly, is the measure of average-case complexity. Time complexities are classified by the nature of the function T(n). For instance, an algorithm with T(n) = O(n) is called a linear time algorithm, and [...]" $\endgroup$
    – Stefan
    Commented Dec 22, 2015 at 16:09
  • 1
    $\begingroup$ I believe it is this book and, in addition to the non-stellar review I just left, there is another dated today, which probably is not a coincidence! $\endgroup$
    – Jason C
    Commented Dec 22, 2015 at 19:46
  • $\begingroup$ That usage of say feels like the least-used definition: To assume or suppose. Think of it as "... , let's say." Still not sure that sentence makes sense. $\endgroup$
    – Roger Krueger
    Commented Dec 24, 2015 at 8:33

2 Answers 2

Reset to default
78
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • 13
    $\begingroup$ The first paragraph made me smile because it is exactly the kind of thing the computer science police would tell you :-) (+1 too, this is a good answer). $\endgroup$
    – Juho
    Commented Dec 21, 2015 at 9:44
  • 3
    $\begingroup$ Thank you so much for your explanation. It is very helpful indeed and now I feel I understand it a bit better (or, at least, don't feel angst in my brain for not understanding that paragraph). I can relax now. $\endgroup$
    – JW.
    Commented Dec 21, 2015 at 13:34
2
$\begingroup$

It sounds like the author is attempting to explain Big O notation, but has renamed it $T$ for no particular reason, and mangled the text completely.

For a good description of Big O notation (as well as little-o and Theta), I recommend the MIT book Introduction to Algorithms by Prof. Leiserson.

It does seem that one important distinction is that $O-notation$ refers to the total complexity of an algorithm, which is typically time, space or both.

(e.g. Some algorithms run slower with larger data sets; some require more storage space with larger data; and some require both more time and more space).

It seems that this $T-notation$ refers only to the time-measurement of an algorithm, and doesn't account for storage requirements.

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ It doesn't sound like they're trying to explain big O at all -- they explicitly talk about theta. $\endgroup$
    – David Richerby
    Commented Dec 22, 2015 at 17:54
  • $\begingroup$ Prof. Leiserson's text specifically describes Theta as a more precise variation on BigO. I realize there may be other definitions of Theta, but the BigO-related theta is the one I'm familiar with. $\endgroup$
    – abelenky
    Commented Dec 22, 2015 at 17:57
  • 2
    $\begingroup$ I don't think this is what's going on. Instead, I suspect it's the common sloppiness of writing "T(n)=n" and assuming (without saying it explicitly) that everyone will infer that T(n) refers to a running time, and specifically the running time of the algorithm they have in mind, and n refers to the size of the input. $\endgroup$
    – D.W. ♦
    Commented Dec 22, 2015 at 20:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.