Asymptotic Notation Questions

MCQ bookmark_border

31.

Upper bound is denoted as _______

A

Ω

B

Θ

C

ω

D

O

Correct Answer: D

None.

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

32.

lower bound is denoted as _______

A

Ω

B

Θ

C

ω

D

O

Correct Answer: A

None.

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

33.

The function f(n)=o(g(n)) if and only if Limit f(n)/g(n)=0 n->∞

A

Little oh

B

Little omega

C

Big oh

D

Omega

Correct Answer: A

None.

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

34.

The function f(n)=o(g(n)) if and only if Limit g(n)/f(n)=0 n->∞

A

Little oh

B

Little omega

C

Big oh

D

Omega

Correct Answer: B

None.

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

35.

Time complexity of given algorithm

 Algorithm Display(A) 
{ 
S:=0.0;
 For i:=0 to n-1 
{ 
S:=S+A[i];
 Return S; 
} 
}

A

4n+4

B

4n²+4

C

2n²+2n+2

D

4n+4

Correct Answer: A

None.

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

36.

Time complexity of given algorithm 

Algorithm:

Sum(A,S) 
{ 
for i:=1 to n-1 
{ 
for j:=2 to n-1
 { 
 S:=S+i+j;
  return S;
   }
 }
 }

A

6n²-14n+4

B

4n²+6n+12

C

6n²+14n+10

D

6n²-14n+10

Correct Answer: D

None.

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

37.

For defining the best time complexity, let f (n) = log n and g (n) = √n,

A

f (n) ∈Ω(g(n)), but g(n) ∉ Ω (f(n))

B

f (n) ∉Ω(g(n)), but g(n) ∈ Ω (f(n))

C

f (n) ∉Ω(g(n)), and g(n) ∉ Ω (f(n))

D

f (n) ∈Ω(g(n)), and g(n) ∈ Ω (f(n))

Correct Answer: B

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

38.

Which of the following asymptotic notations correctly describes the relationship between the functions \(f(n) = n^3 + 100n^2\) and \(g(n) = n^4\)?

A

\(f(n) = O(g(n))\)

B

\(f(n) = \Omega(g(n))\)

C

\(f(n) = \Theta(g(n))\)

D

\(f(n) = \omega(g(n))\)

Correct Answer: A

The correct answer is A. \(f(n) = O(g(n))\).

🔑 Key Points

• Big O notation (\(O\)): \(f(n) = O(g(n))\) if there exist positive constants \(c\) and \(n_0\) such that \(0 \le f(n) \le c \cdot g(n)\) for all \(n \ge n_0\).
• To determine the relationship, we can evaluate the limit: \(\lim_{n \to \infty} \frac{f(n)}{g(n)}\).
• For \(f(n) = n^3 + 100n^2\) and \(g(n) = n^4\), the limit is \(\lim_{n \to \infty} \frac{n^3 + 100n^2}{n^4} = \lim_{n \to \infty} \left(\frac{1}{n} + \frac{100}{n^2}\right) = 0\).
• Since the limit is \(0\), it implies that \(f(n)\) grows strictly slower than \(g(n)\). This means \(f(n) = O(g(n))\) and \(f(n) = o(g(n))\) are true.
• It also implies that \(f(n) \ne \Omega(g(n))\), \(f(n) \ne \Theta(g(n))\), and \(f(n) \ne \omega(g(n))\).
• Among the given options, \(f(n) = O(g(n))\) is the only correct statement.

Check Answer report_problem Report forum Discussion