Big O notation

Question 1

How can you measure efficiency

Answer 1

By the total number of executions of assignments

Question 2

What is the time complexity of a linear search

Answer 2

O(n)

Question 3

What is the time complexity of a binary search

Answer 3

O(log(n))

Question 4

What is the time complexity of a bubble sort

Answer 4

O(n^2)

Question 5

What is the time complexity of a merge sort

Answer 5

O(nlog(n))

Question 6

What is a tractable problem

Answer 6

A problem that can be solved in a polynomial time or better

Question 7

What does intractable mean

Answer 7

The problem cannot be solved within a reasonable amount of time. An example being O(2^n) or O(n!)

Question 8

What is a heuristic approach

Answer 8

Technique that guides the algorithm into good choices.
It sacrifices accuracy in exchange for a solution within a reasonable time