Data Structures and Algorithms MCQ - Performance Analysis of Algorithms and Recurrences

51 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;
}

The given function is recursive so the equivalent recursion equation is

All the level sums are equal to n. The problem size at level k of the recursion tree is n^{2– k} and we stop recursing when this value is a constant.
Setting n^2–k = 2 and solving for k gives us
2^{– k}log₂n = 1
2^k = log₂n
k = log₂ log₂n
So T(n) = θ(log₂ log₂n)

52 An array of n numbers is given, where n is an even number. The maximum as well as the minimum of these n numbers needs to be determined. Which of the following is true about the number of comparisons needed?

Since,
2n – c = average number of comparison needed.
1.5 n – 2 = number of comparison in case.
n log₂n = also doesn't conform with number of comparison needed.

53 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) denote the number of times the for loop is executed by the program on input n. Which of the following is TRUE?

Upper bound may be √n times it gets executed. Lower bound may be that if gets executed only once or twice.

54 Arrange the following functions in increasing asymptotic order:
A. n^1/3
B. eⁿ
C. n^7/4
D. nlog⁹n
E. 1.0000001ⁿ

B & E are exponential functional
so {B, E} > {A, C, D}
* for larger value of n E > B.
* A < C (clearly power is less)
* D < C for larger value of n
So A < D < C < E < B.

55 When n = 2^2k for some k ≥ 0, the recurrence relation T(n) = √2 T(n/2) + √n , T(1) = 1 evaluates to:

Given if n = 1 then T (1) = 1
So put n = 1 in all options only option (A) gives 1