4.4.4.2 Maths for understanding Big-0 notation and 4.4.4.3 Order of complexity

Question 1

What is Big-O notation?

Answer 1

it is a way of defining how efficient an algorithm is by how “fast” it will run. You determine the algorithm’s notation by the worst case scenario run time.
see http://bigocheatsheet.com/

Question 2

What is constant time?

Answer 2

O(1)
using a constant-size lookup table
One of the most ideal complexities

Question 3

What is logarithmic time?

Answer 3

O(logn)
Finding an item in a sorted array with a binary search or a balanced search tree
One of the most ideal complexities

Question 4

What is linear time?

Answer 4

O(n)

Finding an item in an unsorted list

Question 5

What algorithms are O(nlogn)?

Answer 5

heapsort or merge sort

Question 6

What is quadratic time?

Answer 6

Multiplying two n-digit numbers by a simple algorithm; bubble sort (worst case
quicksort (worst case),
selection sort or insertion sort

Question 7

What is exponential time?

Answer 7

O(2^n)
Finding the (exact) solution to the travelling salesman problem

Question 8

What is factorial time?

Answer 8

O(n!)

Solving the travelling salesman problem via brute-force search;