Analysis, Design and comparison

Question 1

What is time complexity?

Answer 1

The amount of time that an algorithm will take to solve a problem

Question 2

What does the Big-O time complexity show?

Answer 2

The maximum amount of time that an algorithm will take relative to the number of inputs

Question 3

What is Big-O(1)?

Answer 3

Constant time complexity - Time taken in independent from the number of inputs

Question 4

What is Big-O(n)?

Answer 4

Linear time complexity - The time taken is directly proportional to the number of inputs

Question 5

What is Big-O(n^k)?

Answer 5

Polynomial time complexity - The time taken is directly proportional to the number of inputs to the power k

Question 6

What is Big-O(2^n)?

Answer 6

Exponential time complexity - The time taken doubles with every additional input

Question 7

What is Big-O(log(n))?

Answer 7

Logarithmic time complexity - The time taken increases at a falling rate

Question 8

Order the time complexities from best to worst

Answer 8

• O(1)
• O(log(n))
  -O(n)
  -O(n log(n))
• O(n^2) / O(2^n)

Question 9

What is space complexity?

Answer 9

The amount of space that an algorithm requires to solve a particular problem

Question 10

What is an algorithm?

Answer 10

A series of steps to solve a problem

Question 11

How can space complexity be reduced?

Answer 11

The algorithm completes all operations on the original piece of data

Question 12

How can time complexity be reduced?

Answer 12

The algorithm completes operations on as few number of items as possible