Algorithms Test 1

Result

Algorithms Test 1

Score
-
out of -
Rank
-
out of -

TIME Taken - -

SHARING IS CARING

If our Website helped you a little, then kindly spread our voice using Social Networks. Spread our word to your readers, friends, teachers, students & all those close ones who deserve to know what you know now.

Weekly Quiz Competition

Question 1
1 / -0

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:

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

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

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

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

Solution

Take very large number in order to compare the asymptotic complexity of the given
If n = 2¹⁰⁰⁰⁰
√n = √2¹⁰⁰⁰⁰>> 1000
log₂n = 10000
1000 = 1000
1000/√n = 1000/√2¹⁰⁰⁰⁰ ≈ 0
Descending order: √n, log₂n, 1000, 1000/√n
Question 2
1 / -0

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

A
O(n.log m)

B
O(k.n.log m)

C
O(k.n.logn)

D
O(k.n.m^1/3)

Solution

Time complexity
int count = 0;
int i, j, k;
for (i = 1; i < = m; i *= 3) // O(log₃ m)
{
for(j = 1; j <= n ; j++) // O(n)
{
while(k--) // O(k)
{
count++;
}
}
}
T(n) = O(log₃ m) × O(n) × O(k) = O(n.k.logm)
Question 3
1 / -0

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");

A
O(m*n )

B
O(m+n)

C
O(X*Y)

D
O(X+Y)

Solution

For First Loop: runs for X times
T(X) = O(X);
For Second Loop: runs for Y times
T(Y) = O(Y);
Total time complexity: T(X) + T(Y)
∴ time complexity = O(X + Y)
Question 4
1 / -0

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

A
O(n)

B
O(n²)

C
O(log n)

D
O(1)

Solution

Binary search is also called a half-interval search. It compares the required value with a middle element.
Generally, space complexity is the extra space that we are needed in the algorithm.
In a binary search, we have just a comparison between the array element and data element to be searched.
Since no extra space is needed: Space complexity: O(1)
Important Points:
In space complexity, an array that contains the original data is not included because it is already given and we have not added any extra space apart from that.
The time complexity of binary search: O(log n)
Question 5
1 / -0

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

A
O(1)

B
O(log p)

C
O(√p)

D
O(p)

Solution

A prime is only divisible by 1 and itself.
It is enough to calculate √p and check a number is divisible or not by other numbers
The complexity of Ispime is O(√p).
Code:
#include<stdio.h>
#include <math.h>
bool Isprime(int);
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;
}
bool Isprime(int p){
int i;
for(i = 2; i <= sqrt(p); i++) \\ O(√p)
{
if(p%i == 0)
return false;
}
return true;
}
Question 6
1 / -0

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

A
Only III

B
Only II and IV

C
I, II and III

D
I, II, III and IV

Solution

\(A = \mathop \sum \limits_{j = 0}^n {j^2}\)
A = 1² + 2² + 3² + 4² + 5² + 6² … n²
\(A = \frac{{n\left( {n\; + \;1} \right)\left( {2n + 1} \right)}}{6}\)
For given expression what holds true
Θ(n³) → average case (true)
O(n⁴) → worst case (true)
Ω(n²) → best case (true)
θ (n⁴) → average case (false)
Option c is true.
Question 7
1 / -0

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\)

A
T(n) = θ(lg(lg²n)lg n)

B
T(n) = θ(lg²nlgn)

C
T(n) = θ(lg² n lg lg n)

D
T(n) = θ(lg(lg n))g n)

Solution

\(T\left( n \right) = 4T\left( {\sqrt n } \right) + lo{g^2}n\)
Consider n = 2^m
m = log n
T(2^m) = 4T(2^m/2) + m²
Put S(m) = T (2^m/2)
S(m) = 4 S(m/2) + m²
Now use master’s theorem :
a = 4 and b = 2, \({m^{log_b^a}} = \;{m^{log_2^4}} = \;{m^2}\)
S(m) = m² + m²
So, Time complexity will be O(m²log m)
Put the value of m
Time complexity will be : O (log²n log (logn))

User

Question Analysis

Correct -
Wrong -
Skipped -

My Perfomance

Score
-
out of -
Rank
-
out of -

Re-Attempt Weekly Quiz Competition

Algorithms Test 1

Result

Algorithms Test 1

Score

-

Rank

-

SHARING IS CARING

Question 1

log2 n, √n, 1000, 1000/√n

√n, log2 n, 1000, 1000/√n

√n, log2 n, 1000/√n, 1000

log2 n, √n, 1000/√n, 1000

Solution

Question 2

O(n.log m)

O(k.n.log m)

O(k.n.logn)

O(k.n.m1/3)

Solution

Question 3

O(m*n )

O(m+n)

O(X*Y)

O(X+Y)

Solution

Question 4

O(n)

O(n2)

O(log n)

O(1)

Solution

Question 5

O(1)

O(log p)

O(√p)

O(p)

Solution

Question 6

Only III

Only II and IV

I, II and III

I, II, III and IV

Solution

Question 7

T(n) = θ(lg(lg2n)lg n)

T(n) = θ(lg2nlgn)

T(n) = θ(lg2 n lg lg n)

T(n) = θ(lg(lg n))g n)

Solution

User

Question Analysis

My Perfomance

Score

-

Rank

-

Results Announcement on: coming Monday

Stay Tuned: We’ll update you on your result via email or SMS.

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

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

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

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

O(k.n.m^1/3)

O(n²)

T(n) = θ(lg(lg²n)lg n)

T(n) = θ(lg²nlgn)

T(n) = θ(lg² n lg lg n)