wayground logo

Free Printable Worksheets

Font size

S
M
L
XL
Worksheets

Asymptotic Notations Practice Questions

Total questions: 58

Worksheet time: 38mins

Name
Class
Date
1.

Which of the following case does not exist in complexity theory?

a)

Best case

b)

•Worst case

c)

•Average case

d)

Null case

2.

•The worst case complexity for insertion sort is _________

•

a)

O(n)

•

b)

O(log n)

c)

•O(n2)

d)

•O(n log n)

3.

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;

•}

a)

Theta (n)

b)

Theta (n^2)

c)

•Theta (n*Logn)

d)

•Theta (nLognLogn)

4.

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

a)

X will always be a better choice for small inputs

b)

•X will always be a better choice for large inputs

c)

•Y will always be a better choice for small inputs

d)

•X will always be a better choice for all inputs

5.

•What is the time complexity of following code:

•int a = 0, b = 0;

•for (i = 0; i < N; i++) {

•a = a + rand();

•}

•for (j = 0; j < M; j++) {

•b = b + rand();

•}

a)

•O(N * M) time,

b)

•O(N + M) time,

c)

None of these

6.

•To measure Time complexity of an algorithm Big O notation is used which:

a)

describes limiting behaviour of the function

b)

•characterises a function based on growth of function

c)

•upper bound on growth rate of the function

d)

•all of the mentioned

7.

•If for an algorithm time complexity is given by O(n) then complexity of it is:

a)

•constant

b)

•linear

c)

•exponential

d)

•none of the mentioned

8.

•If for an algorithm time complexity is given by O(1) then complexity of it is:

a)

•constant

b)

•polynomial

c)

•exponential

d)

•none of the mentioned

9.

Consider the following three claims

1. (n + k)m = Θ(nm), where k and m are constants

2. 2n + 1 = O(2n)

3. 22n + 1 = O(2n)

Which of these claims are correct ?

a)

(A) 1 and 2

b)

(B) 1 and 3

c)

(C) 2 and 3

d)

(D) 1, 2, and 3

10.

What is the time complexity of this code

int a = 0, i = N;

while (i > 0)

{

a += i;

i /= 2;

}

a)

O(N)

b)

O(Sqrt(N))

c)

O(N / 2)

d)

O(log N)

11.

The complexity of Binary search algorithm is

a)

O(n)

b)

O(log n)

c)

O(n2)

d)

O(n log n)

12.

What is the time complexity of following code:

int a = 0;

for (i = 0; i < N; i++) {

for (j = N; j > i; j--) {

a = a + i + j;

}

}

a)

O(N)

b)

O(N*log(N))

c)

O(N * Sqrt(N))

d)

O(N*N)

13.

What is the time complexity of following code:

int i, j, k = 0;

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

for (j = 2; j <= n; j = j * 2) {

k = k + n / 2;

}

}

a)

O(n)

b)

O(nLogn)

c)

O(n^2)

d)

O(n^2Logn)

14.

A linear function takes the form

a)

f(n) = an + b

b)

f(n) = an2 +bn + c

c)

f(n) = alog2n

d)

f(n) = a + b

15.

Find the slowest time complexity

a)

O (n)

b)

O (n^2)

c)

O (n!)

d)

O (2^n)

16.

The number of executions grows extremely quickly as the size of the input increases

a)

Exponential Time

b)

Linear Time

c)

Polynomial Time

d)

Constant Time

17.

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

a)

X will be a better choice for all inputs

b)

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

c)

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

d)

Y will be a better choice for small inputs

18.

Consider the following functions:

f(n) = 2^n

g(n) = n!

h(n) = n^logn

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

a)

f(n) = O(g(n)); g(n) = O(h(n))

b)

f(n) = omega (g(n)); g(n) = O(h(n))

c)

g(n) = O(f(n)); h(n) = O(f(n))

d)

h(n) = O(f(n)); g(n) = omega (f(n))

19.
Consider this list of numbers: 3 4 6 7 8 9. If the number 9 was to be found using a linear search, how many comparisons need to be made?
a)
6
b)
3
c)
8
d)
4
20.
What is the main disadvantage of a binary search compared to a linear search?
a)
It requires the data to be in order
b)
It requires more memory
c)
It does not execute as quickly with larger data sets
d)
Not all CPUs are capable of executing the algorithm
21.
Consider this list of numbers: 3 4 6 7 8 9. If the number 9 was to be found using a linear search, how many comparisons need to be made?
a)
6
b)
3
c)
8
d)
4
22.
Consider this list of numbers L: 3 4 5 6 7 8 9. Which number would be checked first in a binary search?
a)
6
b)
3
c)
9
d)
4
23.

What is the worst case running time of the above pseudo code?

a)

O(n)

b)

O(n log n)

c)

O(n2)

d)

O(n3)

24.
What is the worst case running time of the above pseudo code?
a)
O(n)
b)
O(n log n)
c)
O(n2)
d)
O(n3)
25.

asymptotic notations represents

a)

space complexity of algo

b)

time complexity of algo

c)

both a and b

d)

none of the above

26.

Big

 Ω\Omega defines

a)

lower bound

b)

upper bound

c)

middle bound

d)

none of the above

27.

This picture represents

a)

big theta noataion

b)

big oh notation

c)

big omega notation

d)

none of the above

28.

Which of the following case does not exist in complexity theory?

a)

Best case

b)

•Worst case

c)

•Average case

d)

Null case

29.

big O represents

a)

best case scenario

b)

worst case scenario

c)

average case scenario

d)

none of the above

30.

What is an Algorithm?

a)

A set of instructions that, when executed, completes a defined task that solves a problem.

b)

The process of breaking apart a problem.

c)

The process of removing unnecessary detail.

d)

A sequence of instructions.

31.

Time Complexity of this program:

def f():

a = 0

for i = 1 to n:

a += i;

b = 0

for i = 1 to m:

b += i;

a)

O(n)

b)

O(m)

c)

O(n+m)

d)

O(n*m)

32.

If for an algorithm time complexity is given by O(1) then complexityof it is:

a)

constant

b)

polynomial

c)

exponential

d)

none of the mentioned

33.

If for an algorithm time complexity is given by O(n) then complexityof it is:

a)

A. constant

b)

B. linear

c)

C. exponential

d)

D. none of the mentioned

34.

To measure Time complexity of an algorithm Big O notation is used which:

a)

A. describes limiting behaviour of the function

b)

B. characterises a function based on growth of function

c)

C. upper bound on growth rate of the function

d)

D. all of the mentioned

35.
What two pieces of information allow you to analyse an algorithm?
a)
Time Complexity
b)
Space Complexity
c)
Size Complexity
d)
Complex Complexity
e)
Simplicity Complex
36.

What order of complexity does this graph represent?

a)

Exponential

b)

Polynomial

c)

Linear

d)

Logarithmic

37.

What order of complexity does this graph represent?

a)

Exponential

b)

Polynomial

c)

Linear

d)

Constant

38.

What order of complexity does this graph represent?

a)

Exponential

b)

Polynomial

c)

Linear

d)

Logarithmic

39.
What does the big-O notation show?
a)
The effectiveness of an algorithm
b)
The amount of time required to solve a particular problem
c)
How difficult a problem is to solve
d)
How many lines of code are required to solve a problem
e)
How quickly a solution can be developed
40.

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

f1(n) = 2^n

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

f3(n) = nLogn

f4(n) = n^(Logn)

a)

f3, f2, f4, f1

b)

f3, f2, f1, f4

c)

f2, f3, f1, f4

d)

f2, f3, f4, f1

41.

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

f1(n) = Logn

f2(n) = n

f3(n) = nLogn

f4(n) = n!

f5(n)=n^2

a)

f3, f2, f4, f1,f5

b)

f3, f2, f1, f4,f5

c)

f2, f3, f1, f4,f5

d)

f1, f2, f3, f5,f4

42.

What is the time complexity of this algorithm?

a)

O(n)

b)

O(2n)

c)

O(log n)

d)

O(n2)

e)

O(1)

43.

What is the time complexity of this algorithm?

a)

O(n)

b)

O(2n)

c)

O(log n)

d)

O(n2)

e)

O(1)

44.

What is the time complexity of this algorithm?

a)

O(n)

b)

O(2n)

c)

O(log n)

d)

O(n2)

e)

O(1)

45.

What is the Big-O Notation of picking a sequence of n balls from a bag of n different coloured balls (the ball is not put back into the bag after being picked)?

a)

O(n)

b)

O(n!)

c)

O(log n)

d)

O(n2)

e)

O(1)

46.

What is the Big-O Notation of a combination lock with n digits, each digit having 1 of 10 possible values?

a)

O(n)

b)

O(10n)

c)

O(log n)

d)

O(n2)

e)

O(1)

47.

The linear/sequential search method to search an element in an array has the complexity of BigO(?)

a)

n

b)

n-1

c)

n^2

d)

n logn

48.

What does a logarithmic time complexity mean?

a)

The time taken to complete an algorithm will increase at a smaller rate as the number of elements inputted.

b)

The amount of time taken to complete an algorithm is proportional to 2 to the power of the number of items inputted.

c)

The amount of time taken to complete an algorithm is proportional to the number of items inputted to the power of n

d)

The amount of time taken to complete an algorithm is independent to the number of inputted elements

49.

What does an exponential time complexity mean?

a)

The amount of time taken to complete an algorithm is proportional to 2 to the power of the number of items inputted.

b)

The amount of time taken to complete an algorithm is proportional to the number of items inputted to the power of n

c)

The amount of time taken to complete an algorithm is independent to the number of inputted elements

d)

The time taken to complete an algorithm will increase at a smaller rate as the number of elements inputted.

50.

What does a polynomial time complexity mean?

a)

The amount of time taken to complete an algorithm is proportional to the number of items inputted to the power of n

b)

The amount of time taken to complete an algorithm is independent to the number of inputted elements

c)

The amount of time taken to complete an algorithm is proportional to 2 to the power of the number of items inputted.

d)

The time taken to complete an algorithm will increase at a smaller rate as the number of elements inputted.

51.

What does a constant time complexity mean?

a)

The amount of time taken to complete an algorithm is independent to the number of inputted elements

b)

The time taken to complete an algorithm will increase at a smaller rate as the number of elements inputted.

c)

The amount of time taken to complete an algorithm is proportional to the number of items inputted to the power of n

d)

The amount of time taken to complete an algorithm is proportional to 2 to the power of the number of items inputted.

52.

which are asymptotic notations

a)

O

b)

Ɵ

c)

Ω

d)

All of above

53.

which asymptotic notations is used for upper bound

a)

O

b)

Ɵ

c)

Ω

d)

All of above

54.

which asymptotic notations is used for lower bound

a)

O

b)

Ɵ

c)

Ω

d)

All of above

55.

which asymptotic notations is used for lower and upper bound

a)

O

b)

Ɵ

c)

Ω

d)

All of above

56.

Can we say big O denotes worst case , theta denotes average case and omega denotes best case

a)

yes

b)

no

c)

may be

57.

An algorithm written recursively have same time complexity when it is written in iterative manner

a)

Always same complexity

b)

Sometimes same complexity

c)

Never same complexity

d)

Can't Say

58.

The most important characteristic of algorithm is

a)

Input

b)

Output

c)

Effective

d)

Finite

e)

Defined

Similar Resources on Wayground

APCSP Exam Review

63 questions

APCSP Exam Review

quiz

Worksheet

•

9th Grade - University

Network Media

62 questions

Network Media

quiz

Worksheet

•

University

ITSM Practice Exam

57 questions

ITSM Practice Exam

quiz

Worksheet

•

University

Unit 4 Study Guide

54 questions

Unit 4 Study Guide

quiz

Worksheet

•

9th Grade - University

DIMA 223 Final Exam (Digital Marketing)

53 questions

DIMA 223 Final Exam (Digital Marketing)

quiz

Worksheet

•

12th Grade - University

IMD222 Memory Module

57 questions

IMD222 Memory Module

quiz

Worksheet

•

University

TIN6_ÔN TẬP HKI_2425

60 questions

TIN6_ÔN TẬP HKI_2425

quiz

Worksheet

•

6th Grade - University

Network Models

60 questions

Network Models

quiz

Worksheet

•

University