Time Left - 10:00 mins

GATE CS 2018 - Algorithms Quiz 1 (Analysis of algorithms)

Attempt now to get your rank among 985 students!

Question 1

The recurrence equation
T (1) = 1
T (n) = 2T (n–1) + n, n ≥ 2
evaluates to

Question 2

Consider the following functions:
f(n)=2ⁿ
g(n)=n!
h(n)=n^logn
Which of the following statements about the asymptotic behaviour of f(n), g(n), and h(n) is true?

Question 3

The running time of the following algorithm
Procedure A(n)
If n<=2 return (1) else return (A(⌈√n⌉));
Is best described by

Question 4

The cube root of a natural number n is defined as the largest natural number m such that m³ ≤ n. The complexity of computing the cube root of n (n is represented in binary notation) is

Question 5

Consider the equation ^∞∑_{i = 1} (1/i) = f(n) and the following statements:
I. f(n) = Θ(log n)
II. f(n) = O(n)
III. f(n) = Ω(n)
IV. f(n) = Ω(lg lg n)
Which among above are correct?

985 attempts
8 upvotes
13 comments

Tags :

GATE & PSU CS Algorithms

Mar 25GATE & PSU CS