Big 0 Notation

Question 1

What are the two types of efficiency ?

Answer 1

Time Efficiency - how fast it runs,
Space Efficiency - how much memory it takes up.

Question 2

How do we analyse efficiency ?

Answer 2

In terms of input size (n)

Question 3

How do we measure running time ?

Answer 3

Using basic operations to keep analysis hardware-independent

Question 4

What is the order of growth ?

Answer 4

O(1) - constant
O(log n) - logarithmic
O(n) - linear
O(n log n ) - linearithmic
O(n^2) - quadratic
O(n^3) - cubic
O(n!) - exponential (very inefficient)

Question 5

What is the worst case ?

Answer 5

Longest time the algorithm can take.

Question 6

What is the best case ?

Answer 6

The Shortest time the algorithm can take.

Question 7

What is the average case ?

Answer 7

The expected time over random inputs.

Question 8

What are the Asymptotic notations ?

Answer 8

Big O - upper bound (worst-case),
Big Omega (Ω) - lower bound (best case),
Big Theta (Θ) - tight bound (average case).