## Theta and Orders of Growth

For all x > n0 g(x) is theta(f(x)) iff there exists c1,c2 such that c1*f(x) <= g(x) <= c2*f(x)

g(x) is O(f(x)) if g(x) <= c f(x) (for some constant c) g(x) is Omega(f(x)) if c f(x) <= g(x) (for some constant c)

Orders of Growth that we care about:

- 1 - Constant
- log n - Logarithmic (no non-constant difference between log_2(n) vs. log_3(n))
- n - Linear
- n^2 - Quadratic
2

^{n - Exponential (could have different exponential such as 3}n)

## Dr Scheme + Lisp discussion:

In the code from the previous class, each time you call `add` you are actually calling {{{(lambda(x y)

- ..(add...)

}}}

We talked about two different ways to do this:

**Option 1:**

- (add (decrement x) (increment y)))

(add 5 4) --> (add 6 3) --> (add 7 2) --> (add 8 1) --> (add 9 0)

Each time, the value of the previous expression is the same as the value of the subsequent one.

**Option 2:**

Alternative is

`(increment (add( x (decrement y)))`:

In this case, `(add 5 4)` --> `(increment (add 5 3))` --> `(increment (add 5 2))` --> `(increment (add 5 1))` --> `(increment (add 5 0))` In this case all of the operations are pending. They're waiting for another operation to finish and then incrementing the returned value.

If I have nothing to do once I get the result back, then I don't need to exist any longer. Scheme is smart enough to realize this and replace original operation with its offspring. Thus the first option is more effiecnt.

Option 1 allows the stack to be 1 regardless of the size of `y` because each operation replaces the previous one. Output of last operation can be passed directly to calling function.

In contrast Option 2 would require a stack of size ~`y`.

### Brief overview of Stack:

- Type of Data Structure
- You only access one end: FI,FO - First In, Last Out
- Effectively you pile stuff on top of it and then unpack it afterwards
- Very easy to build with a list structure

Fencepost error if you end up being off by +/- 1 in indexing. Order of Growth doesn't care about +/- 1, so Lynn doesn't really care about it. Contrast with a math course in which precision matters.

Top S --> returns top element of the stack

To code a Stack you need: {{{pop Empty ->error pop (push x S) --> S top (push x S) --> x}}}

cons cell

_ (first) |
_ (rest) |

{{{(first (cons a b)) --> a (rest (cons a b)) --> b}}}

`(cons 1 (cons 2 ( cons 3 '())))`

Inside computer this is represented as:

[1][-->] --> [2][-->]-->[3][nil]

Empty Set is

`'()`,`null`,`nil`depending on Scheme implementation.

would require a special case exception so that you know to read the `cdr` as a value instead of a pointer to the rest of the set. That is why improper lists exist because you might actually want to be able todo it.

- A pair is a totally legitimate data structure.
`(cons 2 3)`prints as`(2. 3)``(1 2 3)`is equivalent to`(1.(2.(3.())))`Scheme is smart enough to convert the

`.(`into " "

`(car (cdr L)) --> (cadr L)`- cadar cddr cadr also exist

### "Authentic" Lisp Names for first and rest.

Lisp was originally designed on a computer with 4 registers. One was used to contain information, the other was used as a pointer to the rest of the data.

first == car (Contents of Address Register)

rest == cdr (Contents of Decrement Register) - "could'er"

### Class Assignment

Build a Scheme program that increments all the items in a list.

Sample Solution:

(define incrementlist (lambda (L) (if (empty? L) () (cons (+ 1 (car L)) (incrementlist(cdr L))) ) ) )

Scheme has procedure called "Map" which maps a procedure onto a list. `(map _ L)` --> new list with `p(x)` for each `x` in `L`. Example:

(define incList (lambda (L) (map (lambda(x)(+ 1 x)) L)))

This will apply `(lambda(x)(+ 1 x))` to `L`.

(define map (lambda (p L) (if (empty? L) L (cons (p (car L)) (map p (cdr L))))))

Procedures are **first-class objects**. They can be passed around, they can be returned, created, or modified.

## Next Steps for Course

- X
- add_one
- subtract_one

- Y
- add_one
- subtract_one

- Compare_to_0

If I want to `compare Y to O`

Y < 0, then

`increment Y`&`increment Y`.Y = 0, then

`return X`.Y > 0, then

`decrement Y`&`increment X`.

This is a finite state machine with 6 possible operations. We're going to show that we can't push pending operations onto the stack.

(define cons (lambda (a d) (lambda (c) (c a d))))

(define car (lambda (x) (x lambda (a d) a)))

It is possible to represent any data structure as a procedure.