Big O Notation

Question 1

Big O notation

Answer 1

Used to compare the time complexity of different algorithms

(Describes how fast the runtime increases as the number of items to be processed increases )

Question 2

Tractable

Answer 2

Problems that can be solved in polynomial time or better

Question 3

Intractable

Answer 3

Problem unable to solved in polynomial time or better ( unsolvable in a reasonable amount of time )

Question 4

Heuristic

Answer 4

Shortcut that sacrifices accuracy and completeness but gives a solution in a reasonable time frame

Question 5

Big O efficiency

Answer 5

N! Intractable
2^n Intractable
n^2 Bubble sort. Tractable
N Linear search tractable
Log n Binary search tractable
N log n. Merge sort tractable