Unit 8 Flashcards
What are the three characteristics of a recursive routine?
- A stopping condition or base case must be included
- The routine must call itself for all values other than the base case
- The stopping condition must be reached after a finite number of calls
T/F: The stopping condition and the base case are the same thing
True
Define base case
A value that stops a recursive routine from calling itself again and causes the call stack to ‘unwind’
How is stack overflow linked to recursive routines?
Recursive routines require a lot of memory space and when the call stack exceeds the designated memory space the program will crash
Define stack overflow
When the memory required for the call stack has exceeded that designated to the sub program
Give an example of where recursive routines are used and why
They can be used in tree traversal as they perform the traversal of either the right or left side of the tree multiple times
What is Big O notation a measure of?
Time complexity
Define Big O notation
A method used by computer scientists to describe the time complexity of an algorithm
What are the 5 time complexities we need to know (in order from least to most complex)?
- Constant time
- Logarithmic time
- Linear time
- Polynomial time
- Exponential time
What type of statement do we use to work out the time complexity of an algorithm?
Assignment statements
How do we simplify the time complexity of an algorithm from multiple terms to just one?
We focus on the most significant term only
What is the time complexity of a binary tree search?
Logarithmic
What is the time complexity of a bubble sort?
O(n ** 2)
What is the time complexity of a linear search?
Linear
Define permutation
The number of ways to arrange a set of items
What are the two types of permutation?
With repetition and with no repetition
What is the difference between the two types of permutation?
Permutations with repetition are were there are the same number of options for each choice (.e.g. numbers on a padlock) where as the number of option reduces with each choice in non repetition permutations (.e.g. removing balls from a bag)
What is the time complexity of permutations with repetition?
O(x ^ n) where x represents the number of options and n represents the number of choices