Algorithms Flashcards
1
Q
Order of common Big(O) complexities
A
- Log(n)
- n
- n*Log(n)
- n^2
- 2^n
- !n
2
Q
Complexity of merge sort
A
n*Log(n)
3
Q
Complexity of binary search
A
Log(n)
4
Q
Approx for:
x + x/2 + x/4 + x/8 + ….
A
2x
5
Q
Approx for:
(n - 1) + (n - 2) + (n-3) + …
A
(n(n-1))/2
6
Q
Sum of power of 2
A
2^(n+1)
7
Q
What is De Morgan’s law (2)
A
!(A or B) = (!A) and (!B)
!(A and B) = (!A) or (!B)
8
Q
What are the problem solving steps (7)
A
Listen
Example
Brute Force
Test
Optimise
Implement
Walkthrough
Implement
9
Q
What are the BUD optimisation steps (3)
A
Bottlenecks
Unnecessary Work
Duplicated Work
10
Q
Formula for permutations of n objects placed at m coordinates where n<=m
A
m!/(m-n)
