Week 2: Complexity Analysis

Question 1

What is Complexity Analysis?

Answer 1

The time required for an algorithm to execute until completion.

Question 2

What is a search problem?

Answer 2

In a standard search problem, we have the inputs: A sequence of numbers a₁, a₂, …, a_n A number to search, q

And the expected outputs: The index in a in which exists q, or NIL if q is not present. ​

Question 3

What is a Linear search?

Answer 3

A linear search checks each element in the sequence sequentially.

This gives a worst case performance of O(n) if q = a_n or if q is not present in the sequence.

This gives an average case performance of n/2. A sorted sequence doesn’t affect the performance.

Question 4

What is a Binary search?

Answer 4

For a binary search, the sequence, a,  must be sorted. This gives a worst case performance of log₂(n). If n is 10 for example, a maximum of 4 array members will need to be checked log₂(10)= 3.3~.

Question 5

How is an algorithm executed using a computational model?

Answer 5

Usually, a generic uniprocessor random-access machine (RAM) is used.

All memory is equally expensive to access.

All instructions are executed one after another, no concurrency.

All reasonable instructions take 1 unit time.

Function calls do not use one unit.

Constant word size.

Question 6

How are the results a function of Input Size?

Answer 6

Sorting: number of input items

Multiplication: number of involved bits

Graph Algorithms: Number of nodes and edges in graph

Question 7

Worst and Average Case

Answer 7

Worst case: Provides an upper bound on running time. A guarantee running time will never be worse than this.

Average case: Provides the expected running time Usually very useful. Care needs to be taken to define what ‘average’ means. It could mean the average input taken from the real world (a median or mode). It could mean the average running time taken from random equally likely inputs.

Question 8

What is Insertion sort?

Answer 8

1. Work left to right.
2. Examine each item and compare it to the items on its left.
3. Insert the item in the correct position on the array.

Worst time complexity is O(n²) if the sequence is sorted decreasing then there will be n number of comparisons and n number of swaps.

Code: InsertionSort(A, n) {for i = 2 to n{ key = A[i] j = i - 1 while (j > 0) and (A[j] > key) { A[j+1] = A[j] j = j - 1 } } }

Question 9

Big-O bound notation?

Answer 9

Big-O notation defines the upper bound for the time complexity of an algorithm.

f(n) is O(g(n)) if there exists positive constants c and n₀ such that f(n) ≤ c • g(n) for all n ≥ n_0.

Question 10

Big-Ω bound notation?

Answer 10

Big-Ω defines the lower bound for the time complexity of an algorithm.

f(n) is Ω(g(n)) if there exists positive constants c and n₀ such that 0 ≤ c • g(n) ≤ f(n) for all n ≥ n₀

Question 11

Big-Θ bound notation?

Answer 11

Big-Θ defines the asymptotic tight bound for the time complexity of an algorithm. f(n) is Θ(g(n)) if there exists positive constants c₁, c₂ and n₀ such that c₂ • g(n) for all n ≥ n₀

If a program by Θ(g(n)) then it is both O(g(n)) and Ω(g(n))

Question 12

Other notation?

Answer 12

o(g(n)) is like < g(n)

O(g(n)) is like ≤ g(n)

ω(g(n)) is like > g(n)

Ω(g(n)) is like ≥ g(n)

Θ(g(n)) is like = g(n)