Algorithms Test...

Consider the following functions from positives integers to real numbers

1000, log₂ n, √n, 1000/√n,

The correct arrangement of the above functions in descending order of asymptotic complexity is:

What is the complexity of the following code?

int count = 0;

int i, j, k;

for (i = m; i >= 0  ; i /= 3)

{

for(j = 1; j <= n ; j++)

{

while(k--)

{

count++;

}

}

What it the time complexity of the below given block of code?

int m,n,X,Y;
for(m = 0; m<X; ++m)
printf("EdTech: ");
for(n = 0; n<Y; n++)
printf("Testbook.com");

What is the space complexity of the following binary search algorithm?

int BinSearch(int a[], int n, int data)

{

int low = 0;

int high = n-1;

while (low <= high)

{

mid = low + (high-low)/2;

if(a[mid] == data)

return mid;

else if(a[mid] < data)

low = mid + 1;

else

high = mid - 1;

}

return -1;

}

Consider a given block of code in C?

int main()
{
int p;
printf("Enter the number: "); 
scanf("%d",&p);
bool x = Isprime(p);
if(x)
printf("p is prime");
else
printf("p is not prime");
return 0;
}

What is the worst-case complexity for the optimal solution of function Isprime() to prove that a number (p) is a prime number or not?

Note: 

Input: p > 1

Considering the equality \(\mathop \sum \limits_{j = 0}^n {j^2} = A\) and the following choices of A:

I. Ω(n²)

II. θ(n³)

III. O(n⁴)

IV. θ (n⁴) 

The equality above remains correct if A is replaced by

Give asymptotic upper and lower bound for T(n) given below. Assume T(n) is constant for \(n \le 2.\;T\left( n \right) = 4T\left( {\sqrt n } \right) + lo{g^2}n\)