Big O notation Flashcards
1
Q
How can you measure efficiency
A
By the total number of executions of assignments
2
Q
What is the time complexity of a linear search
A
O(n)
3
Q
What is the time complexity of a binary search
A
O(log(n))
4
Q
What is the time complexity of a bubble sort
A
O(n^2)
5
Q
What is the time complexity of a merge sort
A
O(nlog(n))
6
Q
What is a tractable problem
A
A problem that can be solved in a polynomial time or better
7
Q
What does intractable mean
A
The problem cannot be solved within a reasonable amount of time. An example being O(2^n) or O(n!)
8
Q
What is a heuristic approach
A
Technique that guides the algorithm into good choices.
It sacrifices accuracy in exchange for a solution within a reasonable time
