theory of computation Flashcards
define the halting problem
-the impossible creation of a program which can conclude whether or not a program will halt given its inputs and description without executing the program
what does the halting problem show
it shows that there are some problems which simply cannot be solved by computers
what is an algorithm
A sequence of steps that can be followed to complete a task and that always terminates.
who proved the halting program could not be done
Alan Turing
what did proving the halting program couldn’t be done show
this dispelled the belief that hardware was the only limit to algorithms
define space complexity
a measure of the amount of memory space needed by an algorithm to solve a particular problem of given input size
define time complexity
a measure of the amount of time needed by an algorithm to solve a particular problem of a given input size
what is constant time/space
O(1)
an algorithm that always takes a constant amount if time or memory space to execute regardless of the input size
what is exponential time/space
O(2^n)
an algorithm whose execution time or required memory space grows exponentially with the input size
intractable- cannot be solved in a useful amount of time
what is the logarithmic time/space
O(log(n))
an algorithm whose execution time or required memory space grows logarithmically with input size
what is linear time/space
O(n)
an algorithm whose execution time or required memory space is directionally proportional to the size of its input
what is polynomial time/space
O(n^k)
an algorithm whose execution time or required memory space is proportional to the input size raised to the power of a constant(k)
order of complexity
constant logarithmic linear polynomial exponential
