M3: Asymptotic Notation

Question 2

What is asymptotic notation used for?

Answer 2

To describe the growth rate of algorithms, particularly how they scale with input size n.

Question 3

What does Big O Notation (O) represent?

Answer 3

Upper Bound

Question 4

Define Big O Notation.

Answer 4

T(n)=O(f(n)) means the function T(n) grows at most as fast as f(n) for large n.

Question 5

When is Big O Notation used?

Answer 5

When we want to provide an upper limit on the growth rate of an algorithm.

Question 6

Give an example of Big O Notation.

Answer 6

5n^2+3n+2=O(n^2)

Question 7

Define Little o Notation.

Answer 7

T(n)=o(f(n)) means the function T(n) grows strictly slower than f(n) as n approaches infinity.

Question 8

When is Little o Notation used?

Answer 8

When the growth rate of T(n) is significantly smaller than f(n).

Question 9

What does Theta Notation (θ) represent?

Answer 9

Tight Bound

Question 10

Define Theta Notation.

Answer 10

T(n)=θ(f(n)) means T(n) grows as fast as f(n) for large n, providing both an upper and lower bound.

Question 11

When is Theta Notation used?

Answer 11

When we want to describe the exact asymptotic behavior of an algorithm.

Question 12

Give an example of Theta Notation.

Answer 12

3n^2+2n+1=θ(n^2)

Question 13

What does Big Omega Notation (Ω) represent?

Answer 13

Lower Bound

Question 14

Define Big Omega Notation.

Answer 14

T(n)= Ω(f(n)) means T(n) grows at least as fast as f(n) for large n.

Question 15

When is Big Omega Notation used?

Answer 15

When we want to provide a minimum bound on the growth rate of an algorithm.

Question 16

Give an example of Big Omega Notation.

Answer 16

2n^2+3n= Ω(n^2)

Question 17

What does Little omega Notation (ω) represent?

Answer 17

Strictly Lower Bound

Question 18

Define Little omega Notation.

Answer 18

T(n)=ω(f(n)) means T(n) grows strictly faster than f(n) as n approaches infinity.

Question 19

When is Little omega Notation used?

Answer 19

When the growth rate of T(n) is significantly larger than f(n).

Question 20

Give an example of Little omega Notation.

Answer 20

n^2=ω(n)

Question 21

What is the type and meaning of O(f(n))?

Answer 21

Type: Upper Bound; Meaning: T(n) grows at most as fast as f(n).

Question 22

What is the type and meaning of o(f(n))?

Answer 22

Type: Strictly Upper Bound; Meaning: T(n) grows strictly slower than f(n).

Question 23

What is the type and meaning of θ(f(n))?

Answer 23

Type: Tight Bound; Meaning: T(n) grows exactly as fast as f(n).

Question 24

What is the type and meaning of Ω(f(n))?

Answer 24

Type: Lower Bound; Meaning: T(n) grows at least as fast as f(n).

Question 25

What is the type and meaning of ω(f(n))?

Answer 25

Type: Strictly Lower Bound; Meaning: T(n) grows strictly faster than f(n).

Question 26

For the function T(n)=3n^2+2n+1, what is O(n^2)?

Answer 26

Growth is at most quadratic.

Question 27

For the function T(n)=3n^2+2n+1, what is o(n^3)?

Answer 27

Growth is strictly slower than cubic.

Question 28

For the function T(n)=3n^2+2n+1, what is θ(n^2)?

Answer 28

Growth is exactly quadratic.

Question 29

For the function T(n)=3n^2+2n+1, what is Ω(n^2)?

Answer 29

Growth is at least quadratic.

Question 30

For the function T(n)=3n^2+2n+1, what is ω(n)?

Answer 30

Growth is strictly faster than linear.