SUNY Geneseo Department of Computer Science

Performance of Alternative Height Algorithms

{Date}

CSci 141, Fall 2003
Prof. Doug Baldwin

Return to List of Lectures

Previous Lecture

Misc

Exam 2 Wednesday (Nov. 19)

Lists and Trees
Rules and format similar to exam 1
Practice Questions on the Web
Will try to post solutions tomorrow

Questions?

Guess at closed form for the "Size" Algorithm in Friday's lecture came mostly from past experience with similar recurrences.

Height Algorithm

    int height()
        if ! this.isEmpty()
            leftHeight = this.left().height()
            rightHeight = this.right().height()
            if leftHeight > rightHeight
                return 1 + leftHeight
            else
                return 1 + rightHeight
        else
            return 0

    int height()
        if ! this.isEmpty()
            if this.left().height() > this.right().Height()
                return 1 + this.left().Height()
            else
                return 1 + this.right().Height()
        else
            return 0

Mini-assignment: what are the performance consequences

Plan

Set up recurrences for each algorithm
Give closed forms asymptotically (Theta(...))

Recurrences

height w/ variables:
- f(0) = 1
- f(n) = 3 + f(n₁) + f(n₂) if n > 0
- Closed form: f(n) = 4n + 1
- This is the recurrence from "size" Friday
- = Theta(n)
[From here on this is pretty much "extra" material -- stuff that you can probably follow, but that I definitely wouldn't expect you to do on your own]
height w/o variables
- recurrence
  - f(0) = 1
  - f(n ) = 4 + 2f(n₁) + f(n₂) if n > 0
  - where n₁ + n₂ = n - 1
- Look at extreme cases
- Worst case, largest f()
  - n₁ big, n₂ small
  - n₁ = n-1, n₂ = 0
  - Rewrite recurrence for this n₁, n₂
    - f(0) = 1
    - f(n) = 5 + 2f(n-1) if n > 0
  - = Theta(2ⁿ)
- Best case - balanced tree
  - n₁ = n₂ = (n-1)/2
  - Rewrite recurrence
    - f(0) = 1
    - f(n) = 4 + 3f( (n-1)/2 ) if n > 0
  - Restrict n to values for which (n-1)/2 is whole, and [ (n-1)/2 ] -1 / 2 whole etc
  - n = 2ⁱ - 1

n = 2ⁱ - 1	f(n)
0 = 2⁰ - 1	1
1 = 2¹ - 1	4 + 3f(0)
	= 4 + 3(1)
3 = 2² - 1	4 + 3f(1)
	= 4 + 3(4+3(1))
	= 4 + 3(4) + 3²(1)

Guess: f(n) = 4 (sum from j=0 to i-2 of 3^j) + 3^i-1
[I added lots of algebraic details below that I didn't have to explain in class]
= Theta( 3^log₂n )
= Theta( (2^log₂3)^log₂n ) [any number can be written as 2 raised to the base 2 log of that number]
= Theta( (2^log₂3 ^log₂n) [for any x, y, z, x^{y^z} = x^yz]
= Theta( (2^log₂n ^log₂3) [switching the order of multiplicands in the exponent]
= Theta( n^log₂3 ) [2^log₂n = n ]
= Theta( n^1.58 )

Inserting new items into a binary search tree

Next Lecture