Big Everything and Proofs

Question 1

Put the following in order of size

• 2ⁿ
• n²logn
• 1
• n^0.5
• nlog²n
• log(n)
• n
• n²
• n³
• nⁿ
• 3ⁿ
• nlog(n)
• n^1.5
• n!

Answer 1

Question 2

What are the 5 different types of asymptotic notation?

Answer 2

Question 3

Roughly speaks, f(n) E of the following means:

Answer 3

Question 4

When building the Big-Oh definition, what is step one?

Answer 4

Question 5

When building the Big-Oh definition, what is step two?

Answer 5

Question 6

What is the official definition of Big-Oh? Also explain it in plain language

Answer 6

Question 7

As we’ve learned in discrete math, the order of quantifiers matter.

Answer 7

Question 8

Changing the definition only, what would be the format of the definition given the following to prove:

Answer 8

Question 9

What is the rough work for the following:

Answer 9

Question 10

What is the actual proof of the following

Answer 10

Question 11

Provide the proof for the following

Answer 11

Question 12

How do you prove that something is NOT big oh? What needs to be done to the definition first?

Answer 12

Question 13

Express the statement in words as well

Answer 13

Question 14

Show the proof for the following

Answer 14

Question 15

What is the definitinon of Big-Omega and what is it in plain language?

Answer 15

Question 16

In general what would a graph look like of Big-Omega?

Answer 16

Question 17

Answer 17

Question 18

What is the theorem for the relationship between Big-Oh and Big-Omega?

Answer 18

Question 19

Answer 19

Question 20

Answer 20

Question 21

What is the official definition of Big-Theta and what does it mean in english?

Answer 21

Question 22

What is the theorem that is equivalent to the definition of Big-Theta?

Answer 22

Question 23

In general, how do you prove Big-Theta using the theorem?

Answer 23

Question 24

Prove the first step

Answer 24

Question 25

Answer 25

Question 26

Prove the following

Answer 26

Do it

Question 27

Prove the following

Answer 27

Do it

Question 28

Prove the following

Answer 28

Do it

Question 29

Prove the following

Answer 29

Do it

Question 30

Prove the following

Answer 30

Do it

Question 31

Prove the following

Answer 31

Do it

Question 32

Prove the following

Answer 32

Do it