Computer Science - Algorithms

The Big O notation describes algorithm efficiency, representing its worst-case time complexity. It determines how performance scales with input size, using "O" followed by a function to indicate the upper bound.

f(x) = ax+ c

f(x) = ax^m + bx + c

f(x) = ab^x

f(x) = a logn x

1. Remove all terms except the one with the largest factor

2. Remove any constants

O(n)

A constant complexity O(1)

Logarithmic O(log n)

Linear O(n)

Polynomial O(n^the number of loops)

Exponential O(2^n)

1. O(1)

2. O(log n)

3. O(n)

4. O(n²)

5. O(2^n)

function linearSearch(namelist,nameSought)

	index = -1

	i = 0

	found = False

	while i < length(namelist) AND NOT found

		if namelist[i] == nameSought then

			index = i

			found = True

		endif

		i = i + 1

	endwhile

	return index

endfunction

O(n)

1. Divide: Split the sorted array in half to find the middle element.

2. Compare: Check if the middle element is equal to the target value.

3. Conquer: If the target is smaller or larger, repeat the search in the corresponding half of the array.

O log n

The steps of a bubble sort algorithm are as follows:

1. Start with an unsorted list of elements.

2. Compare adjacent elements in the list.

3. If the elements are in the wrong order, swap them.

4. Repeat steps 2 and 3 until the entire list is sorted.

5. Continue this process for each element in the list.

6. The largest element will "bubble" to the end of the list after each pass.

7. Repeat steps 2-6 until the list is completely sorted.

for i = 0 to n - 2

for j = 0 to (n – i - 2)

if a [j] > a[j + 1]

temp = a[j]

a[j] = a[j + 1]

a[j + 1] = temp

endif

next j

next i

O(n^2).

The steps for an insertion sort are as follows:

1. Start with the second element in the list.

2. Compare the second element with the first element and swap if necessary.

3. Move to the third element and compare it with the previous elements, swapping if necessary.

4. Repeat this process for all remaining elements, comparing each with the previous elements and swapping if necessary.

5. Continue until all elements are in their correct sorted positions.

This process effectively "inserts" each element into its proper place within the sorted portion of the list.

procedure insertionSort(aList)

for j = 1 to len(aList) - 1

nextItem = aList[j]

i = j – 1

while i >= 0 and aList[i] > nextItem

aList[i + 1] = aList[i]

i = i - 1

endwhile

aList[i + 1] = nextItem

next j

endprocedure

The steps for a merge sort algorithm are as follows:

1. Divide the unsorted list into n sublists, each containing one element (base case).

2. Repeat the following steps until there is only one sublist remaining: a. Merge adjacent sublists by comparing the smallest elements and placing them in sorted order. b. Continue merging sublists until all sublists are merged into a single sorted list.

3. The resulting sorted list is the final output.

Merge sort has a time complexity of O(n log n) and is a popular sorting algorithm due to its efficiency and stability.

O(n log²n)

The steps of the Quick Sort algorithm are as follows:

1. Choose a pivot element from the array.

2. Partition the array into two sub-arrays, one with elements smaller than the pivot and one with elements larger than the pivot.

3. Recursively apply steps 1 and 2 to the sub-arrays.

4. Combine the sorted sub-arrays to obtain the final sorted array.

Note: The choice of pivot element can vary, and there are different partitioning schemes that can be used.

O(n²)

The steps for a depth-first graph traversal are as follows:

1. Choose a starting vertex.

2. Mark the starting vertex as visited and Place it on the stack

3. Add the neighbour to the visited list

4. Continue until there are no unvisited nodes ,so you have to backtrack removing items from the stack

5. Repeat steps 2-4

6. Remove all nodes from the stack, meaning that every node has been visited

function dfs(graph, currentVertex, visited)

	append currentVertex to list of visited nodes

	for vertex in graph[currentVertex]

		if vertex not in visited then

			dfs(graph, vertex, visited)

		endif

	next vertex

	return visited

endfunction

1. Finding a path between vertices

2. Solving puzzles such as mazes

3. Job scheduling

The steps of a breadth-first traversal are as follows:

1. Start by visiting the root node.

2. Enqueue the root node.

3. While the queue is not empty, do the following:

   • Dequeue a node from the queue.

   • Visit the dequeued node.

   • Enqueue all of its adjacent nodes that have not been visited.

4. Repeat steps 3 until the queue is empty or all nodes have been visited.

This process ensures that nodes at the same level are visited before moving to the next level.

1. Finding the shortest patch between two points

2. Web crawlers use BFT to analyse sites you can reach by following links

O(n²)