First Exam Material Flashcards
1
Q
f = O(g(n)
A
Steps f less than or equal to g
2
Q
f = Omega(g)
A
Steps f greater than or equal to g
3
Q
f = Theta(g)
A
Steps f equal to g
4
Q
O(n^a) compared to O(n^b)
A
O(n^a) > O(n^b) if a > b
5
Q
O(n^5) compared to O(3^n)
A
O(3^n) > O(n^5)
6
Q
O(3^n) compared to O(2^n)
A
O(3^n) > O(2^n)
7
Q
O(log n ^3) compared to O(n)
A
O(n) > O(log n ^3)
8
Q
O(n^2) compared to O(n log n)
A
O(n^2) > O(n log n)
9
Q
log(x*y)
A
log(x) + log(y)
10
Q
log(x/y)
A
log(x) - log(y)
11
Q
log(x^y)
A
y log x
12
Q
f(x) = log(x)
A
f’(x) = 1/x
13
Q
integral(log(x))
A
x(log(x) - 1)
14
Q
Satisfy +/- propertyn
A
For even n
1st n/2 are opposuite of n/2
wn0 = -wnn/2
wn1 = -wnn/2+1
…..
wnn/2-1 = -wnn-1
15
Q
For n=2k
A
(nth roots)2 = n/2 roots
(wnj)2 = (1, 2π/n j)2 = (1, (2π/(n/2))j = wn/2j
(wnn/2+j)2 = (-wnj)2 = wn/2j
