# Computational complexity

When we talk about the complexity of an algorithm, we generally refer to the worst-case scenario (Big O) and the best case scenario (Big Omega).

Tendency of an algorithm is dictated by its highest-order term.

Asymptotic notation – a family of notations invented by Paul Bachmann, Edmund Landau and others (Big O , Big Omega, Big Theta …)

**O(1) Constant time**

Asymptotically constant. Always takes a single operation in the worst case.

Example:

Accessing the value of a variable.

```
int four_for_you(int array[1000])
{
return 4;
}
int add_two_nums(int a, int b)
{
return a + b;
}
```

**O(log n) Logarithmic time**

**O(n) Linear time**

Always takes n operations in the worst case.

Example:

– searching for a number in the array. Look every element to see if the number is there.

– counting the number of characters in a string from first to last one.

–

**O(n log n) Linearithmic time**

**O(n^2) Quadratic time**

**O(n^c) Polynomial time**

**O(c^n) Exponential time**

**O(n!) Factorial time**

Runtime of a for loop

```
// O(m)
for (int j = 0; j < m; j++){
// loop body that runs in O(1)
}
// O(p^2)
for (int j = 0; j < p; j++){
for (int k = 0; k < p; k++){
// loop body that runs in O(1)
}
}
```

# Big O notation

REVIEW https://www.youtube.com/watch?v=0PPR5RWhoFI

Big O notation is a mathematical notation that describes the limiting behavior of a function when the argument tends towards a particular value or infinity.

Upper bound of steps.

Bubble sort, Selection sort and Insertion sort O(n^2)

# Ω Omega notation

Lower Bound notation

# θ Theta notation

When the best and worst cases are the same.

O = Ω

Example:

length of the string in a variable

# Algorithms

https://www.toptal.com/developers/sorting-algorithms

## Linear Search

Iterate across the array form left to right, searching for a specified element.

**Pseudocode**

Repeat starting at the first element

If the first element is what we are looking for, stop

Otherwise mowe to the next element

**Big O** We have to look through the entire array of n elements, either because the target element is the last element of the array or it doesn’t exist in the array at all.

**Big Omega** The target element is the first element of the array, and so we can stop looking immediately after we start.

```
linearSearch(key, array[]):
for (i = 0; i < length(array); i++):
if (array[i] == key):
return i
return -1
```

O(n)

Omega(1)

## Binary Search

The idea of the algorithm is to divide and conquer, reducing the search area by half each time, trying to find a target number. The algorithm assumes that the array M is sorted in ascending order.

BinarySearch(key, array[], min_index, max_index)

Array size 7:

[1 2 3 ] (4) [5 6 7]

O(log 7 / log 2)

You are looking for an element x inside an array M, which contains n elements.

**Pseudocode**

Repeat until the (sub)array is of size 0:

calculate the middle point of the current (sub)array.

If the targer is at the missle, stop.

Otherwise, if the target is less than what’s at the middle, repeat, changing the end point to be just to the lift of the middle.

Otherwise, if the target is greater than what’s at the middle, repeat, changing the start point ro ve just to the right of the middle.

** In other words**

Set low to 0, high to n – 1.

If low > high, x does not exist in M and the algorithm terminates.

Set mid to (low + high) / 2.

If M[mid] < x, set low to mid + 1 and go to step 2.

If M[mid] > x, set high to mid – 1 and go to step 2.

M[mid] equals x and the algorithm terminates.

**Code**

```
binarySearch(key, array[], min, max):
if (max < min):
return -1
else:
midpoint = findMidPoint(min, max)
if (array[midpoint] < key):
binarySearch(key, array, midpoint + 1, max)
elif (array[midpoint] > key):
binarySearch(key, array, min, midpoint-1)
else
return midpoint
```

**Big O** We have to divide a list of n elements in half repeatedly to find the target element, either because the target element will be found at the end of the last division or doesn’t exist in the array at all.

** Big Omega** The target element is at the midpoint of the full array, and so we can stop looking immediately after we start.

O(log n)

Omega(1)

### Binary Search Tree

**Properties**

– The left subtree of a node only contains values that are less than or equal to the node’s value

– The right subtree of a node only contains values that are greater than or wqual to the node’s value

– Both left and right subtrees of a node are also binary search trees.

Minimum value: Always go to the left

Max value: always go to the right

Inorder traversal: going from the min value to the max by traversing the tree.

## Bubble Sort

Move higher valued elements generally towards the right and lower value elements towards left.

**Pseudocode**

Set swap counter to a non-zero value (eg. -1)

Repeat until the swap is 0:

Reset swap counter to 0

Look at each adjacent pair

If two adjacent elements are not in order; swap them and add one to the swap counter

Notice that after the first pass the highest number is in its place.

Swap counter tells us when the array is sorted – whene there are no more swaps.

**Big O** The array is in reverse order; we have to “bubble” each of the n elements all the way across the array and since we can only fully bubble one element into position per pass we must fo this n times

**Big Omega** The array is already perfectly sorted and we make no swaps on the first pass.

O(n^2)

Omega(n)

Sum: compare two, swap if needes, compare next who, swap if needed.

End the sort when there are no more swaps.

## Selection sort (search for smallest)

Find the smallest unsorted element and add it to the end of the sorted list.

**Pseudocode**

Repeat until no unsorted elements remain

Search the unsorted part of data to find the smallest value

Swap the smallest found value with the first element of the unsorted part

**Big O**: we have to iterate over each of the n elements of the array (to find the smallest unsorted element) and we must repeat this process n times, since only one element gets sorted on each pass.

**Big Omega**: Exactly the same. We can’t say the array is sorted until we go through all elements.

(n-1) + (n-2) + … +1 = n(n-1) / 2 = (n^2 – n) / 2 = n^2/2 – n/2 = O(n^2)

Divide the list in sorted portion and unsorted portion

```
for i = 1 to n-1
min = i
for j = i + 1 to n
if array[j] < array[min]
min = j
if min != i
swap array[min and array[i]
```

## Instertion sort

Build sorted array in place, shifting elements out of the way id necessary to make room as you go.

**Pseudocode**

Call the first element of the array sorted

Repeat untill all elements are sorted

Look at the next unsorted element. Insert into the sorted portion by shifting the requisite number of elements.

**Big O:** The array is in the reverse order; we have to shift each of the elements n positions each time we make an insertion

**Big Omega:** The array is already sorted and we simply keep moving the line between unsorted and sorted as we examine each element.

O(n^2)

Omega(n)

```
for i = 1 to n - 1
element = array[i]
j = i
while (j > 0 and array[j -1] > element)
array[j] = array[j-1]
j = j -1
array[j] = element
```

Sum: Going through the array linearly. Sorting array one at the time. Move multiple elements if needed

## Heap sort

O(n*log(n))

## Quicksort

O(n^2)

- Pick the last element in the array and call it a pivot

…

## Merge sort

The idea of the algorithm is to sort smaller arrays and then combine those arrays together (merge them) in sorted order.

Merge sort levarages recursion.

Recursive sort

O(n* log n)

** Pseudocode**

On input of n elements

if n < 2

return

else

sort left half of elements in the array

sort right half of elements in the array

merge sorted halves

if sentence runs in constant time T(n) = O(I) if n < 2

Sort left half of elements T(n/2)

Sort right half of elements T(n/2)

Merge O(n)

```
T(n) = T(n/2) + T(n/2) + O(n) = O(n log n) if n >=2
```

**Big O** We have to split n elements up and then recombine them, effectively doubling the sorted subarrays as we build them up.

** Big Omega** The array is already perfectly sorted. But we still have to split and recombine it back together .

O(n log n)

Omega(n log n)

Sources:

https://courses.edx.org/courses/course-v1:HarvardX+CS50+X/ Week 3