4.4.4 Classification of Algorithms Flashcards
What is used to compare algorithms?
Space and time complexity.
What are the four methods of comparing algorithms?
Factorials (permutations)
Big O notation.
Function mapping
Time vs space complexity.
What is big o notation used for?
Describing the complexity of an algorithm, always assuming the worst case scenario.
What is the big o notation for linear search.
O(n)
What is the big O notation for bubble sort.
O(n2)
What is the big o notation for merge sort
O(nlog(n))
What is the big O notation for binary search?
O(log(little2(n))
What are the two measurements of the limitations of computation.
Tractability and intractability
Define a tractable problem
Have a polynomial or less time solution.
On a graph, what do all functions, except constant, grow by?
All functions grow, as the input increases.
What is the big o notation for constant?
O(c)
What is the big O notation for logarithmic?
O(log(small2(n))
What is the big o notation for linear?
O(n)
What is the big o notation for linear logarithmic?
O(nlog(n))
What is the big o notation for polynomial?
O(n^2)
What is the second big o notation for polynomial, in terms of checking 3D coordinates?
O(n^3)
What is the big o notation for exponential?
O(2^n)
What is the big o notation for factorial?
O(n!)
What is a tractable problem?
A problem that can be solved within a useful period of time.
What is an intractable problem?
Effectively insoluble problems as they take too long to solve which is unlikely to be useful - due to the limitations of computation.
How can intractable problems be solved?
Using heuristics to provide an approximate solution to a problem.
What is the problem with using heuristics as a method of solving intractable problems.
They are not optimal and are only approximate solutions.
What does the halting problem demonstrate?
That there are some problems which can not be solved by computers.
What are factorials useful for?
Calculating permutations.
