SUNY Geneseo Department of Computer Science

Asymptotic Notation

Previous Lecture

Misc

Hand out Lab 7

First hour exam is this Friday (Mar. 4)

• Object oriented algorithms, recursion, induction, recurrences, asymptotic notation
• 3 - 5 short answer questions
• Will put practice test on Web
• Open book, notes, computer
• Closed person
• Whole class period

Questions?

Asymptotic Notation

Section 9.2

Some differences betweenn algorithms matter more than others

Fastest-growing term is most important -- e.g., n² vs n vs constant

Asymptotic notation indicates rough proportionality

Initialization and ranking algorithms?

• Initialization: set all elements of arrray to some fixed value

    for each index into A
        A[index] = value

• Ranking: identify each element in array by order, 1st, 2nd, 3rd

    for each index i in A
        countOfSmallerElements = 0
        for each index s in A
            if A[s] <= A[i]
                countOfSmallerElements = countOfSmallerElements + 1

What about looking for values and proving asymptotic equivalence?

• Example: n² + 3n = Θ(n²)
  • 2ⁿ - 1 = Θ(2ⁿ)
• Formally n² + 3n = Θ(n²) iff
  • c1 n² <= n² + 3n <= c2 n²
  • (when n>=n1, n>=n2 respectively)
• Start with c1, c1 = 1
  • n² <= n² + 3n, as long as n >= 0
  • i.e., n1 = 0
• How about c2?
  • c2 = 2?
  • Is n²+3n <= 2 n² for big enough n?

• Solve n²+3n <= 2 n²
  • n + 3 <= 2 n (divide by n)
  • 3 <= n
• i.e., n2 = 3
• But we could have picked c2 = 17
  • n² + 3n <= 17 n²
  • n + 3 <= 17 n
  • 3 <= 16 n
  • 3 / 16 <= n

Next

Data structure and lists

Read Sections 11.1 and 11.2

Next Lecture