GATE 2024 algorithm Rank Booster Quiz 21

Consider the following recursive function:

int Fun (int array [], int n)

{

           int S=0;

           if(n==0)

           return 0;

           S=Fun (array,n - 1)      

           if (array[n – 1]<=0)

           S=S+100

           return S;

}

What is the worst case time complexity of the above function?

Consider a function f(n) defined recursively as f(n) =  f(n-1) + f(n-2). The space complexity for the runtime stack called implicitly for the calculation of f(n) is ?

int get (int n)

{

if (n<=0)

return;

get (n - 1);

get (n - 3);

printf ("%d", n);

}

If T(n) = Number of functions calls for get(n) then which of the following is recurrence equation of T(n), for n > 0?

Consider an array of n elements with sorted order, if any element i appears more than half the number of element, what is the time complexity to count the number of occurrences of i?

Consider the following functions:

f(n) = 2^log₂ⁿ

g(n) = nlog₂n

h(n) = n^1/log2n

Which of the following statements about the asymptotic behavior of f(n), g(n) and h(n) is true?

Consider the following code :
main()
{
for(i=1 ;i<=n; i= 20*i)
 {
for(j=1 j<=n; j++)
  {
if(n%j==0)
   {
k=1
while(k<=n)
    {
a=b+c;
k=k+1;
    }
   }
  }
 }
}
Assuming "n" to be a prime number , find the Time Complexity of the code?

The running time of an algorithm is represented by the following recurrence relation:

if n <= 3 then T(n) = n

else T(n) = T(n/3) + cn

Which one of the following represents the time complexity of the algorithm?