1
GATE CSE 2003
+1
-0.3
Consider the following three claims
I. (n + k)m = $$\Theta \,({n^m})$$ where k and m are constants
II. 2n+1 = O(2n)
III. 22n = O(22n)
Which of those claims are correct?
A
I and II
B
I and III
C
II and III
D
I, II and III
2
GATE CSE 2003
+1
-0.3
In a heap with n elements with the smallest element at the root, the 7th smallest element can be found in time
A
$$\Theta (n \log n)$$
B
$$\Theta (n)$$
C
$$\Theta(\log n)$$
D
$$\Theta(1)$$
3
GATE CSE 2003
+2
-0.6
The cube root of a natural number n is defined as the largest natural number m such that $${m^3} \le n$$. The complexity of computing the cube root of n (n is represented in binary notation) is
A
O(n) but not O(n0.5)
B
O(n0.5) but not O((log n)k) for any constant k > 0
C
O((log n)k) for some constant k > 0, but not O((log log n)m) for any constant m > 0
D
O((log log n)k) for some constant k > 0.5, but not O((log log n)0.5)
4
GATE CSE 2003
+1
-0.3
The usual $$\Theta ({n^2})$$ implementation of Insertion Sort to sort an array uses linear search to identify the position where an element is to be inserted into the already sorted part of the array. If, instead, we use binary search to identify the position, the worst case running time will
A
remain $$\Theta ({n^2})$$
B
become $$\Theta (n{(\log \,n)^2})$$
C
become $$\Theta (n\log \,n)$$
D
become $$\Theta (n)$$
GATE CSE Papers
2023
2022
2021
2020
2019
2018
2017
2016
2015
2014
2013
2012
2011
2010
2009
2008
2007
2006
2005
2004
2003
2002
2001
2000
1999
1998
1997
1996
1995
1994
1993
1992
1991
1990
1989
1988
1987
EXAM MAP
Joint Entrance Examination