What about space?

• In addition to how LONG an algorithm takes, we must also consider how much SPACE it needs
• How many method calls does it require, i.e., how much stack space is required?
• How many additional objects must it create, i.e., how much heap will be consumed?
• Space complexity is the amount of memory used by an algorithm (including the input to the algorithm) to execute and produce the result

Linear Search

• Search starts from the first element in an array or list and moves sequentially until it finds a match to the given key
• In an array, if the key is matched to an element the index of the element is returned – if no match perhaps -1 is returned
• In a list a reference to the element would be returned on a match, null otherwise
• Linear searches are simple to implement but are slow. For a list with N elements the average number of elements to search would be N/2
• We say that linear search is O(n)

Binary Search

• Array or list must be sorted first
• Start by examining the element at the half-way point
  • If the key you are trying to match is greater than that element it MUST be in the latter half of the array/list
  • If the key we are trying to match is less than the element, it MUST be in the first half of the array/list
• Each time we break the array in half, toss the half we can ignore, then do it again
• Each time we reduce the problem by half
• For N elements the Big O time is O(log 2 N)
• Compared to linear search of O(n), if N=1024 then linear search=1024, binary search=10

Sorting Algorithms

• We categorize sorting algorithms according to a few metrics:
  1. Stability (do subsets of sorted elements remain relative): the relativity between elements survives the algorithm
  2. Memory usage: does it need additional space (RAM)??
  3. Computational complexity (worst vs average behaviour): does it work for large values of n or smaller n values? depends on needs and cases…
  4. Internal structure (swap-, merge-, or tree-based): How it fundamentally works?