Algorithms and Complexity Flashcards
Define an algorithm
A finite set of computational steps that transform input into output
Why do we use algorithms?
Algorithms are effective methods for solving a class of problems
What are common properties of algorithms?
- The inputs to an algorithm must be finite
- The inputs to an algorithm represent instances of the problem
- An algorithm should produce the correct outcome
- An algorithm should terminate
Give examples of algorithm formats
Text, pseudocode, flowcharts, and computer code
What makes an algorithm better than another?
We evaluate algorithms based on their space and time complexity
Define space complexity
The amount of memory required by an algorithm to run to completion
What are the two types of the memory that is required by an algorithm?
The fixed and the variable memory
Define the fixed part of memory needed by an algorithm
The amount of memory required to store certain data/variables whose size is independent of the input to the algorithm
Define the variable part of memory needed by an algorithm
The amount of memory required to store variables whose size is dependent on the input to the program
Define time complexity
The theoretical relationship between the time an algorithm will take to run and the size of its input expressed as a function of the size of the inputs
What factors effect runtime?
The size of inputs, the organisation of the inputs, the optimal operating temperature and the number of processor cores
What case do we consider when evaluating the runtime of an algorithm?
The worst case scenario
Why is it rare to have an algorithm with the best time and space complexity?
Often in decreasing the time or space complexity we increase the other meaning that we either need to work out whether our program should prioritise speed or memory or we need to balance the two equally
Why would we not focus on the worst case scenario with regards to runtime?
If the worst case scenario is very rare there is little point in considering it in which case we would consider the average case
Describe an experimental method of determining the runtime of a program
Running the program for a range of inputs and plotting the runtime
Why do we rarely use an experimental approach to determine the runtime of a program?
You need to implement the algorithm for every input and also ensure that the running conditions are exactly the same for every test
What is an alternative methods to determining how long an algorithm will take to run that is not experimental?
Operation counting
What problem do we face with operation counting?
We need to determine what counts as one operation independent of which programming language it is in because there are differences between programming languages
What does operation counting mean?
Counting how many operations are in an algorithm by tracing it through and working out how many will be executed for different inputs
Why do we have different cases when analysing runtime using operation counting?
The runtime is not just dependent on the number of operations but also on the organisation of the input
What does the notation T(n) mean?
The overall program time as a function of n
How do we determine the average case for the runtime of a program if we cannot determine the runtime for every instance of inputs?
We work out the average number of times an instruction will be executed using the Nth partial sum equation and then use this to determine the average runtime
What is the worst case time complexity for a linear search?
T(N) = 3N + 3
How does a sentinel search work?
It checks to see whether the desired element is at the end of the list, if it is then it’s returned, if not then it sets the last item in the list equal to the desired element. This means that you do not have to perform the check to see whether you are out of bounds.
What is the worst case time complexity for a sentinel search?
T(N) = 2N + 3
What is the worst case time complexity for a binary search?
T(N) = C1 + C2log(N)
What does the growth of functions describe?
How the runtime for a function increases as the number of input elements increases
What does Big-Ohm represent?
The best case time complexity
What does Big-O represent?
The worst case time complexity
What does Big-Theta represent?
The average time complexity
