2.?.? (Big O Notation)

Question 1

What is the Big O Notation?

Answer 1

• A measure of the complexity of an algorithm

Question 2

What is O(1) - Constant?

Answer 2

• The operation will always take the same amount of time, regardless of the data set
• Straight line graph with no gradient

Question 3

What is O(n) - Linear?

Answer 3

• The operation time will increase proportionally as the data set increases
• Straight line graph with any gradient -O(3n)- but is always simplified to O(n)

Question 4

What is O(n^2) - Polynomial?

Answer 4

• The operation complexity is the square of the size of the data set
• Right side of a quadratic graph

Question 5

What is O(2^n) - exponential?

Answer 5

• The operation complexity doubles with each item of data added
• Right side of an exponential graph

Question 6

What is O(log n ) - Logarithmic?

Answer 6

• The operation complexity grows very slowly as the data set increases
• Always in base 2
• Graph increases then plateaus

Question 7

What is O(n!) - Factorial?

Answer 7

• The operation complexity grows very quickly as the data set increases
• e.g. brute force password cracking
• Graph increases at a steep gradient