19.1 Algorithms

• Linear search

• Binary search

• Insertion sort

• Bubble sort

• Abstract Data Types (ADT)

  	Find an item	Insert an item	Delete an item	Key features only
  Linked list	✓	✓	✓
  Binary tree	✓	✓
  Stack		✓	✓
  Queue		✓	✓
  Graph				✓

Show how it is possible for ADTs to be implemented from another ADT: linked list, binary tree, stack, queue, dictionary

• Linked list can be implemented by defining a record consisting an item and a pointer

• Then populating an array of that type

Different algorithms which perform the same task can be compared by using criteria, including use of Big O notation to specify time and space complexity

Big O order of time complexity

• O(1): an algorithm that always takes the same time to perform the task
  • e.g. deciding if a number is even or odd

• O(N): an algorithm where the time to perform the task will grow linearly in direct proportion to N, the number of items of data the algorithm is using
  • e.g. a linear search

• O(N²): an algorithm where the time to perform the task will grow linearly in direct proportion to the square N, the number of items of data the algorithm is using
  • e.g. bubble sort, insertion sort

• O(2ᴺ): an algorithm where the time to perform the task doubles every time the algorithm uses an extra item of data
  • e.g. calculation of Fibonacci numbers using recursion

• O(logN): an algorithm where the time to perform the task goes up linearly as the number of items goes up exponentially
  • e.g. binary search

Big O order of space complexity

• O(1): an algorithm that always uses the same space to perform the task
  • e.g. any algorithm that just uses variables, for example d = a + b + c

• O(N): an algorithm where the space to perform the task will grow linearly in direct proportion to N, the number of items of data the algorithm is using
  • e.g. any algorithm that uses arrays, for example a loop to calculate a running total of values input to an array of N elements

19.2 Recursion

Essential features of recursion

• A process using a function or procedure that is defined in terms of itself and calls itself

• Base case: a terminating solution to a process that is not recursive

• General case: a solution to a process that is recursively defined

• The statements after the recursive function call are not executed until the base case is reached, this is called winding

• When the base case is reached, this is called unwinding