 [FrontPage] [TitleIndex] [WordIndex]

## 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
• 2n - Exponential (could have different exponential such as 3n)

## Dr Scheme + Lisp discussion:

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

}}}

We talked about two different ways to do this:

Option 1:

• (add (decrement x) (increment y)))

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:
[-->] --> [-->]-->[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)

### "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
• subtract_one
• Y
• 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.

2013-07-17 10:43