Asymptotic Notations - II Starter Quiz

Consider the recurrence function:

T(n)=

Then T(n) in terms of notation is?

Which of the given choices is the correct time complexity of the following code?
for (k = 1; k < (n + 1); k++)
 for (m = 1; m < (n + 1); m + = k)

x = x + 1;

Consider the following statement:

S₁ : f(n) = O(f(n)²)

S₂ : If f(n) = Ω(g(n)) then f(n)=O(g(n))

S₃ : If f(n) O(g(n)) then g(n) O(f(n))

Which of the following statements are always true?

Given below are some recurrence relation and some asymptotic complexities:

What is the time complexity of following code ?

Which of the given options provides the increasing order of asymptotic complexity of functions f1, f2, f3 and f4?

  f1(n) = 2ⁿ

  f2(n) = n^3/2

  f3(n) = nLogn

  f4(n) = n^{log n}

Consider the following three claims

1. (n + k)^m = Θ(n^m), where k and m are constants
2. 2^{n + 1} = O(2ⁿ)
3. 2^{2n + 1} = O(2ⁿ)

Which of these claims are correct ?