4.4.4 - ToC (Classification of algorithms) Flashcards
How can the efficiency of an algorithm be measured
- Time
- Space
Explain what is meant by time complexity
The number of steps taken to complete an algorithm
Explain what is meant by space complexity
The amount of memory an algorithm takes up to complete
What are the three scenarios when determining the complexity of a problem
- Worst-case scenario
- Best-case scenario
- Average-case scenario
What scenario does the big-o use
- The worst case scenario
What are the 5 classification of big-o
- O(1) Constant Complexity
- O(n) Linear Complexity
- O(nˣ) Polynomial Complexity
- O(xⁿ) Exponential Complexity
- O(log n) Logarithmic Complexity
What affect does the magnitude of the input have on the time taken an O(1) complexity algorithm
The time doesnt grow as the input size increases
What affect does the magnitude of the input have on the time taken an O(n) complexity algorithm
the time taken grows at the same rate as the magnitude of the input size grows.
What affect does the magnitude of the input have on the time taken an O(nˣ) complexity algorithm
time taken grows at a faster rate than the magnitude of the input size grows.
What affect does the magnitude of the input have on the time taken an (xⁿ) complexity algorithm
time taken grows at a much faster rate than the magnitude of the input size grows.
What affect does the magnitude of the input have on the time taken an O(log n) complexity algorithm
time taken halves as the magnitude of the input size grows
What factors limit what can be computed
- Hardware
- algorithmic complexity
When does hardware limit algorithms
When the hardware doesnt have enough memory for the algorithms
What algorithms have a BigO of O(n)
- Linear Search
- Binary Search Tree
What algorithm have a BigO of O(log n)
- Binary Search
What algorithms have a BigO of O(nˣ)
- Bubble sort
- Insertion sort
- Quick Sort
What algorithm have a BigO of O(n log n)
- Merge Sort
What algorithms have a space complexity of O(1) and why
- Bubble Sort
- Insertion Sort
No more arrays are made during the computation
What is the space complexity of Merge Sort
O(n)
What is the space complexity of Quick Sort
O(log n)
What is a tractable problem
Any problem that is solvable in polynomial time or less, meaning that the algorithm will run quick eneogh for it to be practical and useful
What is an intractable problem
Any problem that can be solved, but cannot be solved in a polynomial time or less
What is the Halting problem
the unsolvable problem of determining whether any program will eventually stop if given particular input.
What is the significance of the Halting Problem
It determines what problems cannot be solved by a computer
What is a heuristic problem
a method of finding a practical solution to an intractable problem that may not be the best
How is a heuristic problem usually solved
- By relaxing some of the constraints to the problem
