Big O / Search / Sort / Stack / Queue Quiz

Sorting and searching

• Comparators
• Arrays and Collections sort method
• TreeSet and TreeMap using Comparator
• Sort methods (Selection, Bubble, MergeSort)
• Search methods (Linear, Binary)

Big O notation to indicate algorithm efficiency

• O(1) - constant , no change
• O(N) - whenever one item is added to the list, one pass will be added to the loop - EX: linear search
• O(N^2) - whenever one item is added to the list, it grow by every item once more - EX: bubble sort, selection sort
• O(Log N) - it grows slowly, and will only increase whenever N doubles. - EX: Binary Search
• O(N Log N) - whenever one item is added to the list, one pass plus a little more will be added to the loop - EX: Merge Sort

Stacks and Queues

• classic methods: add/push, remove/pop, isEmtpy, peek, size
• ability to figure out algorithms to change stacks and queues with other stacks and queues to hold
  • navigate through a queue, pushing the items back on top.
  • navigate through a stack, pushing the items into a holding stack and then placing them back on theoriginal stack
  • reverse a stack by placing on a queue and back onto a stack
• Stack/Queue loop control
  • while(!?.isEmpty()) or
  • for the size of a structure. - often needing to extract the original structure size into a variable first