Reminders

• DONT FORGET TO NODE SPLIT AFTER PUSHING UP AN ELEMENT IN 2-3 TREE
• Remember heaps must be complete! Can't be spindly!
• For WQU, To increase the height by 1, must double the nodes
• Worst case WQH number of nodes is $2^H$
• Max 2-3 tree must have 2 in each node

Iterators

has methods hasNext() and next()

Implementation

Asymptotics

• Big O: bounded above
• Big Θ: tight bounds
  • Big O = Big Ω
• Big Ω: bounded below

General Ideas to Keep in Mind

• If there are nested for loops, how are the incrementing / stopping conditions related to each other?
  • Inner loop independent of outer loop (Often multiply runtimes)
  • Inner loop dependent on outer loop (Useful to use a summation)

The two magic formulas