Q1- What is the time complexity of the following recursive function:
int DoSomething(int n)
{
if (n <= 2)
return 1;
else
return (DoSomething (floor(sqrt(n))) + n);
}
(A) theta(n)
(B) theta(nlogn)
(C) theta(logn)
(D) theta(loglogn) (GATE – 2007)
(d)
The recursive relation formed is
T(n) = T(√n) + 1
Let n = 2m
T(2m) = T(2m/2) + 1
T(2m/2) = T(2m/4) + 1
T(2m/4) = T(2m/8) + 1
Let m = 2a for some a
T(2^2^a) = T(2^2^(a-1)) + 1
T(2^2^(a-1)) = T(2^2^(a-2)) + 1
…
T(2^2^1) = T(2^2^0) + 1
T(2^2^0) = 1
—————————
T(2^2^a) = 1 + 1 + 1 + … + 1 (a+1 times)
T(2^2^a) = a + 1
T(2^m) = log(m) + 1
T(n) = loglog(n) + 1
T(n) = Theta(loglog(n))
Q2- Consider the following C code segment:
int IsPrime(n)
{
int i,n;
for(i=2;i<=sqrt(n);i++)
if(n%i == 0)
{ printf(“Not Prime\n”);
return 0;
}
return 1;
}
Let T(n) denotes the number of times the for loop is executed by the program on input n. Which of the following is TRUE?
(A) T(n) = O(sqrt(n)) and T(n) = Omega(sqrt(n))
(B) T(n) = O(sqrt(n)) and T(n) = Omega(1)
(C) T(n) = O(n) and T(n) = Omega(sqrt(n))
(D) None of the above (GATE – 2007)
(b)
Let’s say n = 100
Then for loop begins with i = 2, and the if condition n%i == 0 will be true, because 100%2 == 0.
So, compiler will write “Not Prime” and go to return 0. “return 0” acts as an exit condition. Basically, “return 0” means “success” — hence, no need to proceed further.
This number is successfully determined to be non-prime, hence no need to go on.” So, we exit for-loop.
Hence, in the best case, we’ll encounter “return 0” at the first iteration, so time complexity is Ω(1).
Now, in the worst case, let’s say n = 101
Compiler will go from i = 2, to i = √n — never encountering “return 0” — means O(√n) times.
Q3- Consider the following function:
int unknown(int n) {
int i, j, k = 0;
for (i = n/2; i <= n; i++)
for (j = 2; j <= n; j = j * 2)
k = k + n/2;
return k;
}
The return value of the function is
(a) θ(n2)
(b) θ(n2*logn)
(c) θ(n3)
(d) θ(n3logn)
Outer loop runs n/2 times, inner loop runs log n time. Also, the returning value k will be executed O(nlogn) times, but in each iteration, k value is incremented by n/2. Overall, return value k of the function will be added n/2 *nlogn with an initial value 0. So, returning value will be O(n2logn).
Q4- T(n) = T(n-1) + n – 1 is equal to
(a) O(logn)
(b) O(nlogn)
(c) O(n2)
(d) None
(c)
T(n) = T(n-1) + n – 1
T(n-1) = T(n-2) + n – 2
T(n-2) = T(n-3) + n – 3
…
T(2) = T(1) + 2
T(1) = 1 + x x is constant and can be negative also
——————————-
T(n) = n-1 + n-2 + n-3 + … + 3 + 2 + 1 + x
T(n) = (n-1)(n-2)/2 + x
T(n) = O(n2)
Q5- In tower of Hanoi problem, with 5 disks, how many numbers of moves are required to sort all the disks?
(a) 15
(b) 31
(c) 41
(d) 26
(b)
Tower of Hanoi problem recurrence equation
T(n) = 2T(n − 1) + 1
T(5) = 2T(4) + 1
T(4) = 2T(3) + 1
T(3) = 2T(2) + 1
T(2) = 2T(1) + 1
T(1) = 1
T(2) = 3
T(3) = 7
T(4) = 15
T(5) = 31