Lec 20: Primitive Recursion vs Stronger Recursion Schemes - CSCI 381 - Goldberg

Administrative Updates

• Deadline for Keywords & MCQ: End of April 27th lecture. Keywords are due per syllabus by May 10th, but new material closes April 27th.
• Research component: Submit one final MCQ and lecture keyword set based on your research paper topic (as if presenting your PowerPoint lecture).
• Final exam structure (not the CUNY First date):
  • Two halves on May 11th and May 13th (ignore CUNY First’s May 18th, 8:30-10:30 AM date)
  • 50% is semester keywords
  • 50% is cumulative material during the semester
• Final week (week of May 18th): No formal meetings or exams. Optional extra lecture may be posted if interest; 100% optional, not graded.
• Grade deadline: School requires grades submitted within 2 days of official final date; attendance during final week helps with clarification if needed.

---

Reminder of Exam Schedule

DATE	DAY OF WEEK	MODE	DESCRIPTION	NOTES
4/15/2026	Wednesday	Brightspace	Lecture on New Material
4/20/2026	Monday	Brightspace	Lecture on New Material
4/22/2026	Wednesday	Brightspace	Lecture on New Material	Lecture Keywords and MCQ are upto today’s lecture, but there is one more lecture “RESEARCH” which is your paper.
4/27/2026	Monday	Brightspace	Lecture on New Material	No Virtual Classroom
4/29/2026	Wednesday	Brightspace	Quiz#3	Brightspace $\rightarrow$ Quizzes
5/4/2026	Monday	Brightspace	Review#1 for Final (quizzes)	I will email you with the protocol for submitting questions.
5/6/2026	Wednesday	Brightspace	Review#2 for Final (cumulative)	I will email you with the protocol for submitting questions.
5/11/2026	Monday	Brightspace	FINAL EXAM: Keyword Exam during regular exam time slot as all semester.
5/13/2026	Wednesday	Brightspace	FINAL EXAM: Cumulative Material Exam during regular exam time slot as all semester.
5/18/2026			Perhaps optional lecture posted with notes if enough interest.	Unrelated to grade and exams

If you have any questions on the above, either wait till next class to ask, or email the class designated email only.

Induction and Recursion

The notion that induction is directly related to recursion has been made before, but we will summarize the key points of those discussions first. The main reason we discuss this here is to explain what the issue Martin Davis was dealing with when he suggested “course of values” recursion to model divide and conquer (and in general actually ANY recurrence relation). This gives us an interesting perspective on induction itself.

The fundamental definition of the basic recursion utilized in the definition of primitive recursive assumes that there is only one base case and the recursive step is based on only one variable’s previous level’s output (as opposed to Ackermann). So, what about Fibonacci and other such recursions (or recurrence relations) that require multiple base cases and a number of previous levels’ outputs (recurrence has access to all previous levels)? Consider Fibonacci which requires access to two previous levels’ outputs: $\text{Fib}(n+1) = \text{Fib}(n) + \text{Fib}(n-1)$; and as just mentioned, recurrence relations have access to ALL previous levels’ outputs. The answer that Martin Davis gives for that is based on discussion (different lecture) workbook on “Encodings”.

Martin Davis argues successfully that in fact Fibonacci and all such recurrences can be rewritten as a (primitive) recursive function that only requires one base case and only one previous level’s output. Yet, how can that be if Fibonacci and other such recurrences require more? The answer is that we can encode a fixed number of values into a single number based on any of the encodings presented in that workbook. Fibonacci only requires two values so the Godel pairing function. (Davis amends Godel by subtracting one for encoding and adding back the one for decoding to achieve this.) If you need more than two values encoded at the same time, then Godel’s Prime Factorization encoding will do nicely (again with Davis’ -/+ 1 amendment).

BUT, divide and conquer (discrete mathematics whose complexity is called the master theorem) and dynamic programming does not fall neatly into the above scheme because the previous level’s outputs are not at a fixed distance away from the current level. Thus, it would not suffice to simply store the last $k$ levels, but rather would require (to be safe) storing (i.e. encoding) ALL previous level’s outputs from which the function can extract a previous level output as needed. For example, in divide and conquer with $N/2$ divisions: if you are at level 16 you need level 8 (8 levels away), but from level 8 you need level 4 (only 4 levels away) - the distance to the required previous level varies as a ratio, it is not fixed. The key is that having access to ALL previous levels’ outputs, you have access to ANY previous level’s output. This ability is called by Davis as a “course-of-values” recursion. Furthermore, if recursion is based on induction, how does the course of values recursion fit in? NOTE: The term “course” here is an equivalent to the term “range” and what is meant here is “a range of values”.

How is simple recursion based on simple (termed weak) induction? They are extremely similar:

• Both require a base case to start the process. (Both recursion and induction call this the “Base Case”.)
• Both require the outcome of a single previous level in order to obtain the outcome of the next level. (Recursion calls this the Recursive Step and Induction calls this the Induction Hypothesis.)
• Both rely on the outcome (i.e. output) of a function, but induction only concerns itself with Boolean Predicates whose outputs are True/False, 0/1, whereas recursion generalizes this to any numerical function whose outputs can be any number.

(This analysis we have discussed in previous lectures.)

What we want to add now is that there is another induction termed “strong induction”, which also has a base case and allows access to ALL previous level’s outcomes or outputs in order to define/evaluate the outcome (output) at the next level. It is precisely this model that “course of values” recursion is based on. How does Martin Davis prove that this type of recursion applied to primitive recursive functions are still primitive recursive? He used the Godel prime factorization encoding and points out that we iteratively just multiply the single number now encoding the last $k$ outputs by the $(k+1)$st prime raised to the power of the current determined value. In this manner, any number of previous level’s outputs can be multiplied in one by one (based on the next available prime number) so that one number is continually maintaining (encoding) all previous levels’ outputs. Then, your actual function can extract (decode) any of the previous level’s outputs it needs.

In summary, even course of values recursion can be encoded so that it too will be simulated by a simple recursion that has only one base case and only one previous level’s output.

This begs the following question (of which I do not have a great answer for):

If course of values recursion which is modeled by strong induction can be encoded/simulated by a simple primitive recursion which is modeled by weak induction, then strong induction is just a modified but equivalent version of weak induction, so in what manner is one “strong” and the other “weak”? I conjecture that historically the mathematicians were unaware of the approach Martin Davis proves and truly thought that the two were that much different.

It turns out, according to Davis, the two are in fact the same - there is no essential difference. Any encoding that can represent all previous levels’ outputs in a single number suffices; the Godel prime factorization is a convenient choice, but other factorizations would also work.

The next tab implements course of values recursion by employing the Godel Prime Encoding.

There is another interesting example from discrete mathematics of a defined recursion that seems to need to recurse by two variables, yet the textbooks seem to claim that simple induction can be applied. The real answer is that although authors like to teach this example using two variables in the recursion, the fact is that only ONE of those variables are required. So this example also is consistent with primitive recursive rules. This example is called the postage stamp problem where a person has face-value $x$ stamps and face-value $y$ stamps; show that a combination of multiples of each will generate all postage $\geq$ some minimum value $z$. The fundamental understanding here is that the two values is only required to set up the base case(s) which are not considered recursive steps from the perspective of computer theory which only goes upward and the recursive step starts at level 1 (but level 0 is the base case). But, after the base case only one type of the face-values stamps is necessary. Whereas the base case can utilize as many variables as you want, the actual recursive steps can ONLY recurse on one variable.

Primes and Course of Values

From previous lectures, we showed that Bounded Minimization is a Primitive Recursive process:

$$\text{MIN}_{t \leq Y}[P(t, X_1, \ldots, X_n)] = \sum_{t=0}^{Y}\left[\prod_{r=0}^{t}[\alpha(P(r, X_1, \ldots, X_n))]\right]$$

What is the first $t \leq Y$ such that $P(t, X_1, \ldots, X_n)$ is TRUE? See the next diagram to understand this formula.

Certain Quantifiers consider only Boolean Predicates instead of returning the first index where $P$ is true.

Universal Quantifier - “For all” $t \leq Y$, $P$ is true:

$$\forall(t \leq Y)\,[P(t, X_1, \ldots, X_n)] \;=\; \prod_{r=0}^{Y}[P(r, X_1, \ldots, X_n)]$$

If any $P$ is False (value 0), then the product will remain zero (False).

Existential Quantifier - “There exists” $t \leq Y$ when $P$ is true:

$$\exists(t \leq Y)\,[P(t, X_1, \ldots, X_n)] \;=\; \alpha\!\left(\sum_{t=0}^{Y}[P(t, X_1, \ldots, X_n)]\right)$$

This summation could only be nonzero if $P$ is true for some $t$ in the range.

Origins of ∀ and ∃

Mathematicians in earlier centuries had limited typographic options, so they repurposed existing letters: $\forall$ (“for all”) is an upside-down A, loosely resembling a U for “universal”; $\exists$ (“there exists”) is a mirrored E for “existential”.

To facilitate certain proofs, these Quantifiers can be modified to operate over a range strictly less than $Y$:

Universal Quantifier (strict) - “For all” $t < Y$, $P$ is true:

$$\forall(t < Y)\,[P(t, X_1, \ldots, X_n)] \;=\; \forall(t \leq Y)\,[P(t, X_1, \ldots, X_n) \lor (t = Y)]$$

This behaves like the above Quantifier except when $t = Y$, which automatically is TRUE for that value; the result being that the truthness of $P$ over the range $t < Y$ is preserved.

Existential Quantifier (strict) - “There exists” $t < Y$, $P$ is true:

$$\exists(t < Y)\,[P(t, X_1, \ldots, X_n)] \;=\; \exists(t \leq Y)\,[P(t, X_1, \ldots, X_n) \land (t \neq Y)]$$

This version does not want $P$‘s value at $Y$ itself to affect $P$‘s values over the range $t < Y$. This is accomplished since when $t = Y$, the “AND” forces a False (value 0) and does not affect the summation of $P$ values over the range $t < Y$.

Divisibility - Does $Y$ divide cleanly into $X$? ($Y \mid X$)

$$Y \mid X \;=\; \exists(t \leq X)\,[Y \cdot t = X]$$

Primality - Is $X$ a prime number?

$$\text{Prime}(X) \;=\; (X > 1) \land \forall(t \leq X)\,[(t = 1) \lor (t = X) \lor \alpha(t \mid X)]$$

$(X > 1)$ since prime numbers must be greater than 1, nor can it be divided by a number $t$ where $1 < t < X$, since 1 and $X$ clearly divide into any natural number $X$.

The next two primitive functions are related to Integer Division.

Integer Division - $\lfloor X/Y \rfloor$

Note: If $X/Y$ does not appear inside $\lfloor X/Y \rfloor$, it refers to real number division.

$$\lfloor X/Y \rfloor \;=\; \min_{t=0}^{X}\,[(t+1) \cdot Y > X]$$

The formula $(t+1) \cdot Y > X$ is equivalent to $(t+1) > \lfloor X/Y \rfloor$. The first time this occurs will be at the point that $t$ is the Integer Division portion of $X/Y$, when $t \leq (X/Y)$ will be closest to $(X/Y)$ and hence the Integer Division.

Remainder (Mod) - $\text{Rem}(X, Y)$

As a reminder:

$$\frac{X}{Y} = \left\lfloor \frac{X}{Y} \right\rfloor + \frac{\text{Rem}(X, Y)}{Y}$$

Then, multiplying both sides by $Y$:

$$X = \left(\left\lfloor \frac{X}{Y} \right\rfloor \cdot Y\right) + \text{Rem}(X, Y)$$

Therefore:

$$\text{Rem}(X, Y) = X ∸ \left(\left\lfloor \frac{X}{Y} \right\rfloor \cdot Y\right)$$

where $∸$ is the cutoff subtraction discussed in previous lectures.

$n$th Prime Number - $\text{Primes}(n)$

We will utilize Bounded Minimization, which is our only primitive recursive search procedure (for the next prime in sequence) if we knew an upper bound value on the next prime number. There is a technicality in that presumably we are performing a Bounded Maximization since we want a higher prime number and not the lower ones which Minimization would tend to find. This can be implemented by adding an explicit constraint to the Bounded Minimization that the prime we are seeking must be strictly greater than the last prime we generated in sequence. This means that we will embed this Bounded Minimization within a simple recursion so that the recursion can keep track for us on the very last (previous level’s) prime.

So, given a sequence of $n$ primes $\text{Primes}(1), \text{Primes}(2), \ldots, \text{Primes}(n)$, what would be an upper bound for the next possible prime number in sequence? Davis proves that the following value suffices:

$$\text{Primes}(n)! + 1$$

The reason for this is that each $\text{Primes}(1), \ldots, \text{Primes}(n)$ cleanly divides $\text{Primes}(n)!$ but cannot divide the "$+1$". So from $\text{Primes}(1), \ldots, \text{Primes}(n)$‘s perspective, $\text{Primes}(n)! + 1$ could be prime. If it is prime, we found a good limit, and even if it is not prime, it could only be that $\text{Primes}(n+1)$ was found between $\text{Primes}(n)$ and $\text{Primes}(n)! + 1$.

Putting this all together:

$$\text{Primes}(0) = 0 \qquad \text{(dummy base case; included only so we have a total function)}$$ $$\text{Primes}(n+1) = \min_{i=0}^{\text{Primes}(n)!+1}\left[\text{Prime}(i) \land i > \text{Primes}(n)\right]$$

Remember: $\text{Prime}(i)$ is the Boolean testing whether or not $i$ is prime, whereas $\text{Primes}(i)$ is the $i$th prime in natural sequence.

Godel Prime Encoding

Consider a finite sequence of numbers $\text{Seq}(1), \ldots, \text{Seq}(n)$. The Godel Prime Encoding of this sequence is:

$$[\text{Seq}(1), \ldots, \text{Seq}(i), \ldots, \text{Seq}(n)] = \text{Primes}(1)^{\text{Seq}(1)} \cdot \ldots \cdot \text{Primes}(i)^{\text{Seq}(i)} \cdot \ldots \cdot \text{Primes}(n)^{\text{Seq}(n)}$$

This is primitive recursive because it is a composition of already known primitive recursive functions: namely, multiplication, power, and now $\text{Primes}()$.

First few primes

$\text{Primes}(0) = 0$ (dummy base case for totality; not prime), $\text{Primes}(1) = 2$, $\text{Primes}(2) = 3$, $\text{Primes}(3) = 5$, $\text{Primes}(4) = 7$, $\ldots$

Primality as an encoding source

Primality is a good source theoretically for encodings due to the fundamental theorem of arithmetic, which states that any natural number can be decomposed uniquely into the product of prime numbers.

For example, encoding $[2, 4, 6, 3]$:

$$[2, 4, 6, 3] = \text{Primes}(1)^2 \cdot \text{Primes}(2)^4 \cdot \text{Primes}(3)^6 \cdot \text{Primes}(4)^3 = 2^2 \cdot 3^4 \cdot 5^6 \cdot 7^3$$

Davis subtracts 1

Davis subtracts one from this number because the Godel prime encoding and pairing functions can only generate positive numbers, and Davis’ theory requires totality. So the encoding produces $(\text{result} - 1)$, and decoding adds the 1 back.

Practical limitation

The Godel prime encoding grows very rapidly - even encoding four small numbers already produces a very large integer. It is theoretically powerful but not practically efficient.

Two useful properties of the Godel Prime Encoding:

a) Extracting the $i$th value from the Godel Prime Encoding:

Suppose $X = [\ldots]$, a Godel Prime Encoding of $n$ values. Then $[X]_i$ represents the $i$th value extracted from $X$. Remember that the $i$th value will be stored in the exponent of $\text{Primes}(i)$, so:

$$[X]_i \;=\; \min_{t=0}^{X}\left[\lnot\left(\text{Primes}(i)^{t+1} \mid X\right)\right]$$

The first time $\text{Primes}(i)^{t+1}$ does not divide $X$ means that $\text{Primes}(i)^t$ did. Thus $t$ is $[X]_i$.

b) Length of the Godel Prime Encoding - how many numbers are encoded?

$$\text{Length}[X] \;=\; \min_{t=0}^{X}\!\left[[X]_t \neq 0 \;\land\; \forall(i \leq X)\left[(i \leq t) \lor ([X]_i = 0)\right]\right]$$

The last value at the length must be nonzero. Any value after the length must be zero.

Course of Values Recursion

Suppose you have a primitive recursive function $f(n)$ that has already generated the outputs $f(0), \ldots, f(n-1)$. The recursive step in function $f(n)$ computes:

$$f(n) = g(n, f(0), \ldots, f(n-1))$$

for some predetermined primitive recursive function $g(n, X_1, \ldots, X_n)$. This requires access to all previous level’s outputs.

If we incorporate Godel Prime Encoding, let $[X_n] = [f(0), f(1), \ldots, f(n-1)]$, then we can rewrite the above as:

$$f(n) = g(n,\, [X_n]) \qquad \text{where } [\cdot] \text{ encodes the } n \text{ previous levels' output values}$$

And then:

$$[X_{n+1}] = [f(0), \ldots, f(n-1)] \cdot \text{Primes}(n)^{f(n)}$$ $$f(n+1) = g(n,\, [X_{n+1}])$$

Why is the first argument $n$, not $n+1$?

One might think the first argument to $g$ should be $n+1$ since we are computing $f(n+1)$, given that the general definition above uses $f(n) = g(n,\, [X_n])$ where $n$ is the current level. But the update step follows the standard primitive recursion convention: $\text{Rec}(Y+1, \ldots) = g(Y, \ldots)$, where $g$ always receives $Y$ (the previous level) when computing level $Y+1$. So in $f(n+1) = g(n,\, [X_{n+1}])$, the $n$ is playing the role of $Y$ - the previous level - which is consistent with how primitive recursion is defined throughout.

In essence, Godel Prime Encoding will encode all previous levels’ outputs by raising the prime generated at the current level to the power of the previous level’s output and “tack that on” to the Godel Prime Encoding passed along so far by simply multiplying this powered value by the previous Godel Prime Encoding obtained.

Loops and the Limits of Primitive Recursion

The definition of Primitive Recursive is based on three Initial Functions and two techniques.

The three Initial Functions:

$$N(X) = 0, \qquad S(X) = X+1, \qquad U_{1,2}(X_1, X_2) = X_1$$

In terms of equivalent programming code:

• $N(X)$: Can be implemented by Assignment (=)
• $S(X)$: Add one can be implemented by ++
• $U_{1,2}(X_1, X_2)$: Can be avoided in code since its purpose is to extract a parameter from a method/function parameter list, and method/function calls are a convenience, not a necessity. Or, if you wish, assignment suffices.

The two Techniques:

• Composition: $z = f(g(x))$ can be implemented by assignment:

  y = g(x)
  z = f(y)

• Recursion:

  $$\text{Rec}(0,\, X_1, \ldots, X_n) = h(X_1, \ldots, X_n)$$ $$\text{Rec}(Y+1,\, X_1, \ldots, X_n) = g(Y,\, \text{Rec}(Y, X_1, \ldots, X_n),\, X_1, \ldots, X_n)$$

  Parameters: level number, previous level’s output; auxiliary variables passed along (nonchanging values).

  Can be implemented by the following for loop, assignment, and the initial functions $N$ and $S$:

  rec = h(X1, ..., Xn);              // rec holds the simulated "output" of Rec at each level
  for (level = 0; level < maxlevel; level++) {
      rec = g(level, rec, X1, ..., Xn);
  }
  // the functions g and h are previously obtained primitive recursive functions.

  rec = h(X1,...,Xn) is an independent call that computes the base case - it is a precursor, not yet part of the recursion loop. In primitive recursion, the base case is not a recursive step; the loop starts only from level 1 onward. This contrasts with typical programming practice, where the base case is usually folded into the recursive structure.

Putting this together, Davis proves that using (a) the For-Loop, (b) Assignment, and (c) Increment by 1 are sufficient to code ANY primitive recursive function. The question is what is missing from accomplishing any partially/computable function from a programming perspective. In terms of the mathematical definition, what is missing is unbounded minimization (as a search process). But for programming, in order to understand Davis’ answer we need to understand the essence of a Loop in programming languages.

Four Components of any Code Loop

1. Control variable must be initialized - This keeps track of which iteration you are up to in the loop / how many times repeated; it is used to control the loops. For example, if you have an array of numbers and want to find the first prime number, keep iterating until you find prime or end of array has been reached. The action is the same - you do not know how many times you will go through the loop; stop when you hit prime.

2. Test Control Variable - This component makes sure the iterated number is eligible and whether you should repeat or not (i.e. exit/break from the loop).

3. Body of the Loop - Action to be repeated or executed found in the center (body) of the loop.

4. Change to the Control Variable - This must occur in order to avoid an infinite loop.

Consider Java loop forms:

// for loop
for (initialization; condition; update) {   // update occurs after body of loop
    // Code to be executed (the body)
}

// while loop
// initialize Control Variable
while (condition) {         // Condition involves the Control Variable
    // Code to be executed (the body)
    // Change to Control Variable
}

// do-while loop
// initialize Control Variable
do {
    // Code to be executed (the body)
    // Change to Control Variable
} while (condition);        // Condition involves the Control Variable is at end of loop

In the current form, the for-loop accomplishes the same as the above while loop. The advantage to the above for-loop is simply organizational - key info all presented in one line at beginning. BUT, the original purpose for the For-Loop was to simply iterate through a sequence of numbers:

For (i := 1 to n) do {
    Print i;
}

The initialization is $i = 1$; the condition involving the control variable is $i \leq n$, which is automatically enforced by the For statement “to n”; the body of the loop is Print i and the change in variable is also embedded in the For statement “1 to n”. (In a certain sense the Java command For (dataType item : collection) is an enhanced form of this.)

Philosophically (programming language perspective):

• The C/++ based For-Loop is similar to a While loop in that the condition/test on the control variable is in essence “searching” for the instance where the condition is met so that the loop will stop and prevent an infinite loop. In the old for loop, the control variable simply served the body - it set the iteration range and the body was the point. In the modern while/for loop, the body serves the control variable: the body’s actions drive the change that determines when the search condition is met.

• Whereas, the original For-Loop was only for repetition (iteration) and NOT as a search procedure. It is PRECISELY this For-Loop that Davis will use in the above implementation of Primitive Recursive functions.

• What is missing in Primitive Recursive to accomplish all Partially/Computable functions: The WHILE LOOP, which is SEARCHING (just as the unbounded minimization, where we do not actually know when and if the control variable condition will stop.)

Putting this together, Davis proves that to code ALL partially/computable functions, one only requires:

• (a) While-Loop (searching)
• (b) For-Loop (repetition)
• (c) Assignment
• (d) Increment by 1

Big-O: Input Length vs Value

The official definition of $O(n)$ is that $n$ refers to the LENGTH of input and not the VALUE of input. If the length of each value inputted is constant then it will be equivalent to the number of inputs, but this could be misleading to some. Again, the true definition is the total length of input, $n$ bits as it were. What is the big difference between LENGTH vs. VALUE and why did analysis of algorithms make this difference when Turing did not? Numerically, the difference in value between LENGTH and VALUE is EXPONENTIAL since for $n$ bits of length, the maximum value it can represent is $2^n - 1$; so essentially, $n$ vs. $2^n$, an exponential difference.

Why wasn’t Turing concerned with this distinction? Turing was interested in solvability and NOT complexity. The issue of linear versus exponential is only an issue of efficiency or complexity; regardless, the algorithm will halt and an output will be produced. That is all Turing was interested in. This is the reason that Davis spends two chapters to prove that Turing computers work on any base of arithmetic for the hardware, even base 1, which only has 1s as the digits. Base 1 is a unique base in that by definition, the value $n$ has $n$ bits (i.e. 1s) to store it. (cf. Godel Sequence Number encoding in the first tab.) So, while a base 1 computer can be Turing compatible, it will NOT be acceptable to analysis of algorithms which differentiates LENGTH vs VALUE of input.

The realization that orders of complexity refer back to the original length of input and not values based on input obtained along the way is the essence to understand why:

• (a) the nonrecursive code for the primitive recursive POWER (exponent) function which involves nested triple for-loops does not have $O(n^3)$ complexity but rather $O(2^n)$ complexity, and
• (b) why Dynamic Programming has complexity that is misunderstood by many.

Before understanding what this has to do with LENGTH vs. VALUE, let us prove that this is the case for (a). Recall that primitive recursive has very few built-in commands and that built-in commands have $O(1)$ time complexity. Of the three initial functions NSU, only $S(x) = x+1$ increases the value. For coding purposes, Davis adds in assignment (=) as one of the built-in commands, also having $O(1)$ time complexity, but assignment only copies values and does not increase them. Thus, $S(x)$ is the only function that increases values.

Now, ADDITION is recursive (iterative) SUCCESSOR, MULTIPLICATION is recursive (iterative) ADDITION, POWER (exponent) is recursive (iterative) MULTIPLICATION. Unraveling these as for loops: addition is a single for loop over successor, giving $O(n)$; multiplication is a single for loop over addition, giving $O(n^2)$; power is a single for loop over multiplication - yielding three nested for-loops all the way down to iterating SUCCESSOR. Now, while we are tempted to say that the time complexity of this triple nested for-loop is $O(n^3)$, a simple reflection on this indicates that that is not possible because if all the loop does is call successor, then each iteration of the loop increases the initial $N(X) = 0$ value by 1, and the maximum number that can be achieved as output is $n^3$ since it was assumed that the triple for-loop operated in $n^3$ time complexity. BUT we know that this implements $\text{POWER}(X, Y) = X^Y$, thus the looping system had to add one (successor) $X^Y$ times to the initial $N(X) = 0$ value, and thus the time complexity must be EXPONENTIAL!

What went wrong? Well, one would need to actually write down all the code to observe what went wrong, but the bottom line is that some of the loops which seem to go from 1 to “m” for some variable “m” or “n” is not based on the original LENGTH of input $n$ as when the process started at initial input time, but rather based on some VALUE picked for $m$ or $n$ that was picked up along the way, and as stated above, the difference between LENGTH and VALUE is EXPONENTIAL. Although beyond the scope of this course, the same issue pops up when analyzing the nonrecursive code for Dynamic Programming. One of the for-loops is typically based on $n$ as a VALUE and not $n$ (they typically will use "$w$" for “weight” as the letter instead of "$n$") as LENGTH. Thus, the double nested for-loop typically used for dynamic programming codes will actually be exponential and not polynomial. Since the double for-loop (or triple for-loop above) “looks” like a polynomial code, some in the literature will call this pseudo-polynomial complexity, but realize that pseudo by definition means FALSE.

Since time complexity defines $O(n)$ in terms of LENGTH of input $n$ and not value, the question is what would $O(n)$ for space resource complexity mean. $n$ in big-O notation usually means the size (length) of the input, not the value passed in to the algorithm. Space complexity of $O(n)$ means that for each of the $n$ input unit elements there will be no more than a fixed number $k$ of bytes allocated to each input element, i.e. the amount of memory needed to run the algorithm grows no faster than linearly at $k \cdot n$.

Review Questions

Q1) Why doesn’t Analysis of Algorithms discuss Base 1 arithmetic if in fact Base 1 hardware can implement a Turing machine?

For an arbitrary natural number $n$, how many bits do you need to store the value $n$?

$$\log_2(n)$$

What is the proportion of $n$ with respect to $\log_2(n)$?

$$\text{exponentiation, since } 2^{\log_2(n)} = n$$

In this case, the more the merrier - the higher the basis the more values that can be stored by the storage area:

$$2^n \ll 3^n \ll 4^n \ll \cdots$$

(Even though analysis of algorithms has a heuristic to drop the last constant, that is only if it appears by itself, but not if it is a power or a base in a polynomial and/or exponential: $n^2 \ll n^3 \ll n^4$.)

What happens if the machine implemented Base ONE arithmetic?

• In this case, the number of bits stored (encoding) = the value it purports to encode.
• BUT, in any other base encoding, the proportion is EXPONENTIATION!

So, when analysis of algorithms states that $O(n)$ time is “based on length (size) of input”, that statement is ONLY VALID in Base 2 and above because in Base 1 the “length” = the VALUE and there is no distinction. Thus, analysis of algorithms will not work in Base 1.

So, Base 1 is Turing Compatible and yes, says Davis, you can build such a machine, but it WON’T work for Analysis of Algorithms theory.

---

Q2) Unraveling the three recursions to obtain $X^Y$ from $N(X) = 0$ and $S(X) = X+1$, yields code involving a triple-nested for-loop based on assignment, null, and successor. Such a triple-nested for-loop we expect to exhibit $O(n^3)$ time complexity. Yet, the only way that the value $X^Y$ can be achieved by adding one (successor) is if it is done an exponential amount of times, indicating that such code requires (at least) exponential amount of time. What went wrong in the analysis?

Consider the following code:

for (i = 0; i < n; i++) {       // O(n)
    System.out.println(i);
}
n = Math.pow(x, y);             // O(1)

Together, the total time complexity is $O(n)$ - Correct, since $n$ was the input.

Now consider the following slightly modified code:

n = Math.pow(x, y);             // O(1)
for (i = 0; i < n; i++) {       // O(n) -- but n is NOT the input here!
    System.out.println(i);
}

Together, the total time complexity labeled as $O(n)$ is Incorrect. This last code is $O(x^y)$, exponential.

The issue is that the definition of time is units of time (CPU cycles) based on LENGTH of INPUT. In the first code, $n$ had to be inputted prior and was the input to that code. In the second code, $x$ and $y$ are the inputs and $n$ is a local variable value obtained later in the code. Thus, in the first code, it is valid to have the time complexity based on $n$. But in the second code, $n$ is NOT the input and thus the time complexity is based on $x$ and $y$.

This same reasoning can be applied to why the primitive recursive implementation of power using a triple-nested for loop is exponential, since it is exponential in the original inputs. The loops use variables declared along the way, and those variables should not be used as part of the time complexity per se.