GATE CSE 2023 | Complexity Analysis and Asymptotic Notations Question 6 | Algorithms

Algorithms

Complexity Analysis and Asymptotic Notations

Marks 1 Marks 2

Searching and Sorting

Marks 1 Marks 2

Divide and Conquer Method

Greedy Method

P and NP Concepts

Dynamic Programming

GATE CSE 2023

MCQ (More than One Correct Answer)

-0

Let $$f$$ and $$g$$ be functions of natural numbers given by $$f(n)=n$$ and $$g(n)=n^2$$. Which of the following statements is/are TRUE?

$$f \in O(g)$$

$$f \in \Omega (g)$$

$$f \in o(g)$$

$$f \in \Theta (g)$$

GATE CSE 2022

MCQ (Single Correct Answer)

-0.33

Which one of the following statements is TRUE for all positive functions f(n) ?

f(n²) = $$\theta$$(f(n)²), when f(n) is a polynomial

f(n²) = o(f(n)²)

f(n²) = O(f(n)²), when f(n) is an exponential function

f(n²) = $$\Omega$$(f(n)²)

GATE CSE 2021 Set 1

MCQ (Single Correct Answer)

-0.33

Consider the following three functions.

f₁ = 10ⁿ, f₂ = n^logn, f₃ = n^√n

Which one of the following options arranges the functions in the increasing order of asymptotic growth rate?

f₁ , f₂, f₃

f₂, f₁, f₃

f₃, f₂, f₁

f₂, f₃, f₁

GATE CSE 2020

MCQ (Single Correct Answer)

-0.33

For parameters a and b, both of which are $$\omega \left( 1 \right)$$,
T(n) = $$T\left( {{n^{1/a}}} \right) + 1$$, and T(b) = 1.
Then T(n) is

$$\Theta \left( {{{\log }_a}{{\log }_b}n} \right)$$

$$\Theta \left( {{{\log }_{ab}}n} \right)$$

$$\Theta \left( {{{\log }_b}{{\log }_a}n} \right)$$

$$\Theta \left( {{{\log }_2}{{\log }_2}n} \right)$$

Previous Next

GATE CSE Subjects

Theory of Computation

Operating Systems

Algorithms

Digital Logic

Database Management System

Data Structures

Computer Networks

Software Engineering

Compiler Design

Web Technologies

General Aptitude

Discrete Mathematics

Programming Languages

Computer Organization