analysis of algorithm (lecture 2)

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

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

How do you measure of the time complexity?

• Big-O notation
• Big-N notation
• N notation
• Small-O notation
• Small-N notation

What does a linear time complexity mean?

• The amount of time taken to complete an algorithm is dependent constantly from the n.

• The time taken to complete an algorithm will increase at a smaller rate as the n.

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

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

What does a constant time complexity mean?

• The amount of time taken to complete an algorithm is independent to the number of inputted elements
• The amount of time taken to complete an algorithm is independent from the number of elements inputted.
• The amount of time taken to complete an algorithm is proportional to the number of items inputted to the power of n
• The amount of time taken to complete an algorithm is proportional to 2 to the power of the number of items inputted.
• The time taken to complete an algorithm will increase at a smaller rate as the number of elements inputted.

What is space complexity?

• The space complexity is the amount of storage space an algorithm takes up
• How many times a certain number (base) is multiplied together to reach another number.
• An algorithm is a series of steps that complete a task

What is the Big-O notation of a linear search algorithm?

• O(n)
• O(log(n))
• O(n2)

What order of complexity does this graph represent?

• Exponential

• Polynomial

• Linear

• Logarithmic

What order of complexity does this graph represent?

• Exponential

• Polynomial

• Linear

• Logarithmic

Which of the following functions has the largest order of growth in terms of n?

• n + log(n)

• n^2 - 3n

• 2^n

• n

Answer explanation

(C) has the largest order of growth, since it grows exponentially with n, while (A) and (B) grow polynomially. (A) has a growth rate of O(n), while (B) has a growth rate of O(n^2), which is still polynomial, but slower than exponential growth.

for i = 1 to n:

   for j = 1 to n:

      print i, j

what is the complexity for this code segment?

• O(n)

• O(n^2)

• O(n log n)

• O(2^n)