First Exam Material

Question 1

f = O(g(n)

Answer 1

Steps f less than or equal to g

Question 2

f = Omega(g)

Answer 2

Steps f greater than or equal to g

Question 3

f = Theta(g)

Answer 3

Steps f equal to g

Question 4

O(n^a) compared to O(n^b)

Answer 4

O(n^a) > O(n^b) if a > b

Question 5

O(n^5) compared to O(3^n)

Answer 5

O(3^n) > O(n^5)

Question 6

O(3^n) compared to O(2^n)

Answer 6

O(3^n) > O(2^n)

Question 7

O(log n ^3) compared to O(n)

Answer 7

O(n) > O(log n ^3)

Question 8

O(n^2) compared to O(n log n)

Answer 8

O(n^2) > O(n log n)

Question 9

log(x*y)

Answer 9

log(x) + log(y)

Question 10

log(x/y)

Answer 10

log(x) - log(y)

Question 11

log(x^y)

Answer 11

y log x

Question 12

f(x) = log(x)

Answer 12

f’(x) = 1/x

Question 13

integral(log(x))

Answer 13

x(log(x) - 1)

Question 14

Satisfy +/- property_n

Answer 14

For even n

1st n/2 are opposuite of n/2

w_n⁰ = -w_n^n/2

w_n¹ = -w_n^n/2+1​

…..

w_n^n/2-1 = -w_n^n-1​

Question 15

For n=2^k

Answer 15

(nth roots)² = n/2 roots

(w_n^j)² = (1, 2π/n j)² = (1, (2π/(n/2))j = w_n/2^j

(w_n^n/2+j)² = (-w_n^j)² = w_n/2^j