CS 4.4. (ALEVEL) - Classification of Algorithms

Question 1

Big O Notation

Answer 1

• Complexity of an algorithm
• Assumes worst case scenario

Question 2

Big O notation examples

Answer 2

Constant -> O(1) e.g. determining if no. is odd/even (time independent of input)

Logarithmic -> O(log n) e.g. binary search (halves no. of items each iteration)

Linear -> O(n) e.g. linear search (worst case scenario goes through each item)

Linear logarithmic -> O(n log(n)) e.g. Merge sort

Polynomial -> O(n^2) e.g. Bubble sort (loop inside a loop)

Polynomial -> O(n^3) e.g. Checking 3d coordinates (A loop inside a loop
inside a loop)

Exponential -> O(2^n) e.g. Recursively calculating Fibonacci no.s (Intractable)

Factorial -> O(n!) e..g Travelers problem (intractable)

Question 3

limits of Computation

Answer 3

Tractable - can be solved, have a polynomial / less time solution

intractable - can be solved, have a exponential/worse time complexity likely use heuristic method (approximations solutions to a problem)

Question 4

Halting problem

Answer 4

• determining when a program will halt without executing it for a given input
• uncomputable (cannot be solves by computers)