Basic Analysis

Question 1

inverses addition and subtraction
𝑥 + 𝑎 − 𝑎
𝑥 − 𝑎 + 𝑎

Answer 1

x

Question 2

inverses multiplication and division
(𝑥 ⋅ 𝑎)/𝑎
(𝑥/𝑎) ⋅ 𝑥

Answer 2

x

Question 3

Inverses Logarithms
a^loga(x)
loga(a^x)

Answer 3

x

Question 4

Definition Big O

Answer 4

f(n) = O(g(n)) if there exist positive constants n0 and c such that for all n >_n0 f(n) <= c g(n) informally f is eventually at most a constant multiple of g

Question 5

Proof that n = O(n^2)

Answer 5

For all 𝑛 ≥ 1, 𝑛 ≤ 1 ⋅ 𝑛^2 (divide both sides by n get 1<= n)

Question 6

Proof 2𝑛 + 8 = 𝑂(n^2)

Answer 6

For all 𝑛 ≥ 4, 2𝑛 + 8 ≤ 1 ⋅ 𝑛^2. (subtract 2n -8 from both sides, get n^ - 2n - 8 >= 0 (n+2)(n-2) >=0)

Question 7

proof 2𝑛 + 8 = 𝑂 (𝑛)

Answer 7

For all 𝑛 ≥ 8, 2𝑛 + 8 ≤ 3 ⋅ 𝑛. (subtract 2ns from both sides, get 8<=n)

Question 8

𝑛” ≠ 𝑂(𝑛)

Answer 8

No matter how you choose 𝑐 and 𝑛0, I can find an 𝑛 ≥ 𝑛! such that
𝑛^2 > 𝑐 ⋅ 𝑛.

Question 9

big omega of 𝑔(𝑛)”)

Answer 9

Definition: 𝑓 𝑛 = Ω 𝑔 𝑛 (“𝑓(𝑛) is big omega of 𝑔(𝑛)”) if
𝑔 𝑛 = 𝑂 𝑓 𝑛 .

Question 10

big theta of 𝑔(𝑛)”)

Answer 10

Definition: 𝑓 𝑛 = Θ(𝑔 𝑛 ) (“𝑓(𝑛) is big theta of 𝑔(𝑛)”) if
𝑓 𝑛 = 𝑂 𝑔 𝑛 and 𝑔 𝑛 = 𝑂(𝑓 𝑛 ).

Question 11

is 5𝑛 Ω(𝑛)?

Answer 11

5𝑛 = Ω(𝑛)

Question 12

is 𝑛! + 3𝑛 Ω(𝑛)

Answer 12

𝑛! + 3𝑛 = Ω( 𝑛)

Question 13

is 5𝑛 Ω(𝑛!)

Answer 13

5𝑛 ≠ Ω(𝑛!)

Question 14

is 5𝑛 Θ(𝑛)?

Answer 14

5𝑛 = Θ(𝑛)

Question 15

is 𝑛! + 3𝑛 Θ (𝑛)?

Answer 15

𝑛! + 3𝑛 ≠ Θ (𝑛)

Question 16

is 5𝑛 Θ(𝑛^2)

Answer 16

5𝑛 ≠ Θ(𝑛^2)

Question 17

Multiplying and Adding with Big O
You will

Answer 17

𝑂 𝑓 𝑛 ⋅ 𝑂 𝑔 𝑛 = 𝑂(𝑓 𝑛 ⋅ 𝑔 𝑛 )
If 𝑓 𝑛 = 𝑂 𝑔 𝑛 , then
𝑂 𝑓 𝑛 + 𝑂 𝑔 𝑛 = 𝑂(𝑔 𝑛 ).

Question 18

a^m

Answer 18

a….a
m times

Question 19

a^-m

Answer 19

1/a^m

Question 20

a^ma^n

Answer 20

a^m+n

Question 21

(a^m)^n

Answer 21

a^mn

Question 22

a^m/a^n

Answer 22

a^m-n

Question 23

loga(xy)

Answer 23

loga(x) + loga(y)

Question 24

a^loga(xy)

Answer 24

xy= a^loga(x)*a^loga(y) = a^logax+loga(y)

Question 25

loga(x^n)

Answer 25

n*loga(x)

Question 26

a^log(x^n)

Answer 26

x^n = (a^logax)^n = a^nlogax

Question 27

log(x/y)

Answer 27

loga(x) - loga(y)

Question 28

a^loga(x/y)

Answer 28

x/y = a^logax/a^logay = a^logax-logay

Question 29

change log to base b from base a