Algorithm - Complexity

What is an Algorithm?

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

• The process of breaking apart a problem.

• The process of removing unnecessary detail.

• A sequence of instructions.

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;

• O(n)

• O(m)

• O(n+m)

• O(n*m)

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

• constant

• polynomial

• exponential

• none of the mentioned

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

• A. constant

• B. linear

• C. exponential

• D. none of the mentioned

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

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;

}

}

• O(N)

• O(N*log(N))

• O(N * Sqrt(N))

• O(N*N)

What two pieces of information allow you to analyse an algorithm?

• Time Complexity
• Space Complexity
• Size Complexity
• Complex Complexity
• Simplicity Complex

What order of complexity does this graph represent?

• Exponential

• Polynomial

• Linear

• Logarithmic

What order of complexity does this graph represent?

• Exponential

• Polynomial

• Linear

• Constant

What order of complexity does this graph represent?

• Exponential

• Polynomial

• Linear

• Logarithmic