Notes for Lab 3

Notes for Lab 3
[Main Page]

Table of Contents
A. Time Complexity
1. Overview
2. Theory
3. Examples
a. Example 1
b. Example 2
c. Example 3
B. Functions as Arguments
C. New Special Forms - Let
1. Format
2. Evaluation

A. Time Complexity

1. Overview

Time complexity is a way for us to examine the efficiency of procedures from a very general viewpoint. We don't care so much about micro-optimizations that make a procedure 5% or 100% faster, but about how the runtime scales up relative to the size of the problem.

2. Theory

From a mathematical viewpoint, we say that a function f(n) is an element of the O(g(n)) if there exists some constants c and n0, such that f(n) < c * g(n) for all n > n0. Essentially this means that g(n) grows at least as fast as f(n) for very large n. However, note that such a statement wouldn't be very useful if we made g(n) very very large. (eg. g(n) = n ^ n ^ n) Thus, what we actually want to say is that f(n) is an element of THETA(g(n)). (replace THETA with the actual capital Greek letter theta) This means that there exist some constants c1, c2, and n0 such that c1 * g(n) < f(n) < c2 * g(n) for all n > n0. What this means is that g(n) grows just as fast as f(n) for very large n.

We would also like g(n) to be in as simple a form as possible. This means that we can drop all constant multipliers, including logarithm bases. (since all you need is a constant multiplier to convert one logarithm base to another) This may all be confusing still, so please read on to the examples.

3. Examples

These examples contain both scheme code for a procedure, and an explanation of how to find the time complexity. It should be noted that all the following examples are recursive procedures. If a procedure is not recursive, (and doesn't have any calls to recursive procedures, etc.) then it most likely has constant time complexity. This depends, of course, on what sort of operations are going on in the procedure, but for the most part, we assume that a single recursive call is constant time. Moreover, we usually just assume that when we write O(g(n), we actually mean THETA(g(n)).

a. Example 1

(define (unknown1 a b)
(if
(= a 0)
1
(unknown (- a 1) b)
)
)

First, you want to look at the base case to determine when recursion ends. In this case, the function will return when the argument a is 0. If we look at the reduction step, we see that on each recursive call, the value of a is decreasing by 1. Thus, the number of recursive calls before recursion ends is going to be roughly a. Since there is nothing going on that would make the runtime of an individual recursive call be non-constant, the time complexity is going to be O(a). Suppose that instead of decreasing a by 1, that it decreases by some other constant, c. Then, we will have roughly a/c recursive calls. However, since c is a constant, we can remove the constant multiplier 1/c and the time complexity is still O(a).

b. Example 2

(define (unknown2 a b)
(if
(= a 1)
1
(unknown2 (/ a 2) b)
)
)

Again, we look at the base case to determine when recursion ends. In this case, the function will return when the argument a is 1. However, the reduction step is no longer decrementing a by a constant, but by a multiplier 1/2. Thus, the number of recursive calls will be roughly log base 2 of a. However, since the base of the logarithm is a constant, we can use the log rules to change the base to any other constant, so we drop the base. Thus, the time complexity for this function will be O(log a).

a. Example 3

(define (unknown3 a b)
(if
(= a 1)
1
(+
(unknown3 (- a 1) b)
(unknown3 (- a 1) b)
)
)
)

Here, instead of one recursive call per reduction step, we have two. What this means is that each recursive call is going to spawn two recursive calls until a hits the base case. This is an example of tree recursion, because the number of recursive calls grows out like a tree. The height of the tree depends on how long it takes the argument to reach the base case, which is a in this case. Also, we can note that each recursive call branches out twice, so the total number of recursive calls is on the order of 2^a. Thus, our time complexity is going to be O(2^a).

Suppose that instead of decrementing a by 1 for each recursive call, we decremented by some other constant. In that case, the height of the tree would no longer be a, but some constant times a. When we exponentiate this new height with the base of 2, then we can pull out the constant factor, so the time complexity remains unchanged.

Additionally, suppose instead of subtracting a constant from a for each recursive call, we divided a by 2. This would mean that the recursion tree would have height log a, which, when exponentiated, gives us a.

Suppose that instead of branching twice, the reduction step made three recursive calls. In this case, the tree would branch out 3 times at every depth, which would result in a time complexity of O(3^a). Note that this time complexity is different from that of O(2^a) because of the base. We can't pull out the base as a constant in the exponential case because there are no constants c and n0 that satisfy the appropriate equations. We can actually prove that exponential time complexities that have different bases are actually all different.

B. Functions as Arguments

Back in the notes for lab 1, we already saw some examples of using functions as arguments. You will see this abstraction in scheme a lot, so you had better become accustomed to it. Since functions/procedures can be both operators and operands in a scheme expression, this means that we can write procedures which will take in lambda expressions or procedures as arguments and apply them.

C. New Special Forms - Let

1. Format for Let expressions

Let is a special form, so it needs to follow a specific format or the substitution model will fail:
(let
(
(<name> <expression>)
(<name> <expression>)
...
)
<body>
)

2. Evaluation for Let expressions

The evaluation order for let is to evaluate each of the <expression> clauses and bind them to the corresponding <name> variables. These definitions are valid inside the <body> clause only. Also, it is important to note that these bindings occur simultaneously. You cannot have a binding that refers to one above it unless the same variables are defined outside the let. If you absolutely need bindings and evaluations to occur sequentially, then use the let*, which has the same format, but differs only in the evaluation.