Free Printable Time and Space Complexity

1.

What is meant by the time complexity of an algorithm?

a)

The amount of time required to solve a particular problem

b)

How difficult a problem is to solve

c)

How many lines of code are required to solve a problem

d)

How quickly a solution can be developed

2.

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

3.

What is space complexity?

a)

The space complexity is the amount of storage space an algorithm takes up

b)

How many times a certain number (base) is multiplied together to reach another number.

c)

An algorithm is a series of steps that complete a task

4.

a)

O(n)

b)

O(m)

c)

O(n+m)

d)

O(n*m)

5.

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

6.

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

7.

What is the time complexity of this algorithm?

a)

O(n)

b)

O(2ⁿ)

c)

O(log n)

d)

O(n²)

e)

O(1)

8.

What is the time complexity of this algorithm?

a)

O(n)

b)

O(2ⁿ)

c)

O(log n)

d)

O(n²)

e)

O(1)

9.

Why is this not a sequence?

Start car

Put in key

Turn key

Drive away

a)

There are spelling mistakes

b)

The instructions are in the correct order

c)

The instructions are in the wrong order

d)

It is a sequence

10.

Which algorithm, will NOT take you from A to B

a)

UP 1

RIGHT 5

UP 2

b)

RIGHT 1

UP 3

RIGHT 4

c)

UP 2

RIGHT 5

UP 1

d)

LEFT 1

UP 3

RIGHT 5

11.

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.

12.

How do we represent the complexity of an algorithm?

a)

Big-R

b)

Big-O

c)

Big-N

d)

Big-A

13.

What order of complexity does this graph represent?

a)

Exponential

b)

Polynomial

c)

Linear

d)

Logarithmic

14.

What order of complexity does this graph represent?

a)

Exponential

b)

Polynomial

c)

Linear

d)

Constant

15.

What order of complexity does this graph represent?

a)

Exponential

b)

Polynomial

c)

Linear

d)

Logarithmic

16.

What is meant by the time complexity of an algorithm?

a)

The amount of time required to solve a particular problem

b)

How difficult a problem is to solve

c)

How many lines of code are required to solve a problem

d)

How quickly a solution can be developed

17.

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

18.

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

19.

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 amount of time taken to complete an algorithm is independent from 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.

e)

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

20.

How do you reduce the space complexity?

a)

Try to complete all of the operations on the same data set

b)

You reduce the amount of embedded for loops, and then reduce the amount of items you complete the operations on i.e. divide and conquer

21.

How do you reduce the time complexity of an algorithm?

a)

You reduce the amount of embedded for loops, and then reduce the amount of items you complete the operations.

b)

Try to complete all of the operations on the same data set

22.

Which of the following is not O(n^2)?

a)

(15^10) * n + 12099

b)

n^1.98

c)

n^3 / (sqrt(n))

d)

(2^20) * n

23.

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

24.

What is the correct Big O notation for an algorithm where the number of operations (steps) can be expressed as:

$4n^3\ +3n\ \log_2n\ \ +\ 273$ n is the size of the input.

a)

$O\left(n^2\right)$

b)

$O\left(3n\right)$

c)

$O\left(\log_2n\right)$

d)

$O\left(273\right)$

e)

$O\left(n^3\right)$

25.

What is the big-Oh runtime of A()?

a)

$O\left(n\log_{ }n\right)$

b)

$O\left(n^2\right)$

c)

$O\left(n\right)$

d)

$O\left(10\cdot n\right)$

26.

What is true for $f\left(n\right)=\log_{ }n$ and $g\left(n\right)=n$ ?

a)

$f\left(n\right)=O\left(g\left(n\right)\right)$

b)

$f\left(n\right)=\theta\left(g\left(n\right)\right)$

c)

$f\left(n\right)=\Omega\left(g\left(n\right)\right)$

27.

What is the maximum number of comparisons that a binary search will apply for an array of length 30.

a)

30

b)

15

c)

5

d)

3

e)

2

28.

What is the big-Oh runtime of B()?

a)

$O\left(n^2\right)$

b)

$O\left(n^3\right)$

c)

$O\left(30\cdot n\right)$

d)

$O\left(n\right)$

29.

Which of these is true for $f\left(n\right)=5n^3+7n+13$ and $g\left(n\right)\ =\ n^5$ ?

a)

$f\left(n\right)=\theta\left(g\left(n\right)\right)$

b)

$f\left(n\right)=\Omega\left(g\left(n\right)\right)$

c)

$f\left(n\right)=O\left(g\left(n\right)\right)$

30.

What is the big-Oh runtime of C(n)?

a)

$O\left(10\right)$

b)

$O\left(n\right)$

c)

$O\left(\frac{n}{2}\right)$

d)

$O\left(\log_{ }n\right)$

31.

Which of the following is the time complexity of insertion sort?

a)

$O(n^2)$

b)

$O(\log n)$

c)

$O(n)$

d)

$O(n\log n)$

32.

Which is true for $f\left(n\right)=2^n$ and $g\left(n\right)=n!$ ?

a)

$f\left(n\right)=O\left(g\left(n\right)\right)$

b)

$f\left(n\right)=\theta\left(g\left(n\right)\right)$

c)

$f\left(n\right)=\Omega\left(g\left(n\right)\right)$

33.

What is the big-Oh runtime of D(n)?

a)

$O\left(n\cdot\log_{ }n\right)$

b)

$O\left(n^2\right)$

c)

$O\left(\log_{ }n\right)$

d)

$O\left(2n\right)$

34.

Which time complexity grows the fastest as the input size increases?

a)

Constant

b)

Linear

c)

Logarithmic

d)

Quadratic

35.

Which time complexity grows the slowest as the input size increases?

a)

Constant

b)

Linear

c)

Logarithmic

d)

Quadratic

36.

Which time complexity has a growth rate that is proportional to the logarithm of the input size?

a)

Constant

b)

Linear

c)

Logarithmic

d)

Quadratic

37.

Which time complexity has a growth rate that is proportional to the square of the input size?

a)

Constant

b)

Linear

c)

Logarithmic

d)

Quadratic

38.

Which time complexity grows at the same rate as the input size?

a)

Constant

b)

Linear

c)

Logarithmic

d)

Quadratic

39.

A program has to find the largest number in a list of 1000 elements. Which time complexity does this operation have?

a)

Constant

b)

Linear

c)

Logarithmic

d)

Quadratic

40.

The number of operations a program has to perform to sort a list of length n is directly proportional to n. What is the time complexity of this program?

a)

Constant

b)

Linear

c)

Logarithmic

d)

Quadratic

41.

A program has to perform an operation that takes the same amount of time, regardless of the size of the input data. What is the time complexity of this operation?

a)

Constant

b)

Linear

c)

Logarithmic

d)

Quadratic

42.

A program has to perform an operation that takes twice as long to complete when the size of the input data doubles. What is the time complexity of this operation?

a)

Constant

b)

Linear

c)

Logarithmic

d)

Exponential

43.

A program has to perform an operation that takes four times as long to complete when the size of the input data doubles. What is the time complexity of this operation?

a)

Constant

b)

Linear

c)

Logarithmic

d)

Exponential

44.

The number of operations a program has to perform to find an element in a sorted list of length n is proportional to the logarithm of n. What is the time complexity of this operation?

a)

Constant

b)

Linear

c)

Logarithmic

d)

Quadratic

45.

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)

46.

The complexity of Binary search algorithm is

a)

O(n)

b)

O(log n)

c)

O(n2)

d)

O(n log n)

47.

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)

48.

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)

49.

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

50.

Find the slowest algorithm:

a)

O (n)

b)

O (n^2)

c)

O (n!)

d)

O (2^n)

51.

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

52.

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

53.

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

54.

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

55.

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

56.

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

a)

O(n)

b)

O(n log n)

c)

O(n²)

d)

O(n³)

57.

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

a)

O(n)

b)

O(n log n)

c)

O(n²)

d)

O(n³)

58.

asymptotic notations represents

a)

space complexity of algo

b)

time complexity of algo

c)

both a and b

d)

none of the above

59.

Big

\Omega

defines

a)

lower bound

b)

upper bound

c)

middle bound

d)

none of the above

60.

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.

61.

How do we represent the complexity of an algorithm?

a)

Big-R

b)

Big-O

c)

Big-N

d)

Big-A

62.

What order of complexity does this graph represent?

a)

Exponential

b)

Polynomial

c)

Linear

d)

Logarithmic

63.

What order of complexity does this graph represent?

a)

Exponential

b)

Polynomial

c)

Linear

d)

Constant

64.

What order of complexity does this graph represent?

a)

Exponential

b)

Polynomial

c)

Linear

d)

Logarithmic

65.

What is meant by the time complexity of an algorithm?

a)

The amount of time required to solve a particular problem

b)

How difficult a problem is to solve

c)

How many lines of code are required to solve a problem

d)

How quickly a solution can be developed

66.

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

67.

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

68.

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 amount of time taken to complete an algorithm is independent from 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.

e)

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

69.

How do you reduce the space complexity?

a)

Try to complete all of the operations on the same data set

b)

You reduce the amount of embedded for loops, and then reduce the amount of items you complete the operations on i.e. divide and conquer

70.

How do you reduce the time complexity of an algorithm?

a)

You reduce the amount of embedded for loops, and then reduce the amount of items you complete the operations.

b)

Try to complete all of the operations on the same data set

71.

Which of the following is not O(n^2)?

a)

(15^10) * n + 12099

b)

n^1.98

c)

n^3 / (sqrt(n))

d)

(2^20) * n

72.

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

73.

You are given a sorted Array A. What is the time complexity to determine if it has two elements whose sum is less than 100?

(a)

74.

What are the time complexities of fun1() and fun2() respectively?

a)

O(n) and O(n)

b)

O(n) and O(2^n)

c)

O(n^2) and O(2^n)

d)

O(n^2) and O(n^2)

e)

O(n^2) and O(n)

75.

Find Time complexity of the following

(a)

76.

Algorithm A and B have a worst-case running time of O(n) and O(log n) respectively. Therefore, algorithm B always runs faster than the algorithm A.

a)

True

b)

False

77.

The asymptotic upper-bound of $f\left(n\right)=20n^2+100n+2$ is $O\left(n^2\right)$

a)

True

b)

False

78.

The asymptotic upper-bound of $f\left(n\right)=2n+2^n$ is $O\left(n^2\right)$

a)

True

b)

False

79.

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

80.

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

81.

What is the time complexity of following 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)

82.

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

83.

Indicate exponential time complexity in terms of big-O notation

a)

O (n)

b)

O (n^2)

c)

O (2^n)

d)

O (log n)

84.

Find the slowest time complexity

a)

O (n)

b)

O (n^2)

c)

O (n!)

d)

O (2^n)

85.

Which notation is consistent for every execution?

a)

O (n)

b)

O (n^2)

c)

O (1)

d)

O (2^n)

86.

Which notation grows in proportion to the size of the input

a)

O (n)

b)

O (n^2)

c)

O (1)

d)

O (2^n)

87.

Which notation would you usually use for a nested loop?

a)

O (n)

b)

O (n^2)

c)

O (1)

d)

O (2^n)

88.

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

89.

The number of executions remains the same regardless of the input size

a)

Exponential Time

b)

Linear Time

c)

Polynomial Time

d)

Constant Time

90.

The number of executions grows quickly by the input being multiplied by the input

a)

Exponential Time

b)

Linear Time

c)

Polynomial Time

d)

Constant Time

91.

For every element, you are doing a constant number of operations, such as comparing each element to a known value.

a)

Quadratic

b)

Linear

c)

Logarithmic

d)

Constant

e)

Exponential

Time and Space Complexity

Total questions: 91

Worksheet time: 1hrs 8mins

Similar Resources on Wayground