Search Header Logo

Quiz on Complexity Analysis of Algorithms

Authored by Mr. Maurya

Computers

University

Used 4+ times

Quiz on Complexity Analysis of Algorithms
AI

AI Actions

Add similar questions

Adjust reading levels

Convert to real-world scenario

Translate activity

More...

    Content View

    Student View

8 questions

Show all answers

1.

MULTIPLE CHOICE QUESTION

30 sec • 1 pt

What is the time complexity of the following function?

int fun(int n) {

int count = 0;

for (int i = n; i > 0; i /= 2)

for (int j = 0; j < i; j++)

count += 1;

return count;

}

O(n*log(n*log(n)))

O(n^2)

O(n)

O(n*log(n))

2.

MULTIPLE CHOICE QUESTION

30 sec • 1 pt

What is the time complexity of the following function?

int fun(int n) {

int count = 0;

for (int i = 0; i < n; i++)

for (int j = i; j > 0; j--)

count = count + 1;

return count;

}

Theta(n^2)

Theta(n*(log(n*log(n))))

Theta(n)

Theta(n*log(n))

3.

MULTIPLE CHOICE QUESTION

30 sec • 1 pt

O(n^2) is the worst-case time complexity, so among the given options it can represent:

All of the above

O(n log n)

O(1)

O(n)

4.

MULTIPLE CHOICE QUESTION

30 sec • 1 pt

Which of the given options provides the increasing order of asymptotic complexity of functions f1, f2, f3, and f4?

f1(n) = 2n

f2(n) = n^(3/2)

f3(n) = n*log(n)

f4(n) = n log(n)

f2, f3, f4, f1

f3, f2, f4, f1

f3, f2, f1, f4

f2, f3, f1, f4

5.

MULTIPLE CHOICE QUESTION

30 sec • 1 pt

What is the time complexity of the following function?

void fun(int n, int arr[]) {

int i = 0, j = 0;

for (; i < n; ++i)

while (j < n && arr[i] < arr[j])

j++;

}

O(n^2)

O(n)

O(n*log(n^2))

O(n*log(n))

6.

MULTIPLE CHOICE QUESTION

30 sec • 1 pt

In a competition, four different functions are observed. If n is the size of input (positive), which function is most efficient? If n is the size of input(positive), which function is most efficient(if the task to be performed is not an issue)?

for(i = 0; i < n; i++)

for(i = 0; i < n; i += 2)

for(i = 1; i < n; i *= 2)

for(i = n; i <= n; i /= 2)

7.

MULTIPLE CHOICE QUESTION

30 sec • 1 pt

What does it mean when we say that an algorithm X is asymptotically more efficient than Y?

X will be a better choice for all inputs except possibly large inputs

X will be a better choice for all inputs except possibly small inputs

X will be a better choice for all inputs

Y will be a better choice for small inputs

Access all questions and much more by creating a free account

Create resources

Host any resource

Get auto-graded reports

Google

Continue with Google

Email

Continue with Email

Classlink

Continue with Classlink

Clever

Continue with Clever

or continue with

Microsoft

Microsoft

Apple

Apple

Others

Others

Already have an account?