Computer Science - Algorithms

What is the Big-O Notation

What is the Big-O Notation

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.

How is a linear function expressed?

f(x) = ax+ c

How is a polynomial function expressed?

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

How is an exponential function expressed?

f(x) = ab^x

How is a logarithmic function expressed?

f(x) = a logn x

What are the two rules to follow to have Big O notation

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

2. Remove any constants

Following Big O notation how is 5+3n+1 expressed

O(n)

What notation does code with no loop often have(Big-O)

A constant complexity O(1)

What notation does code with a halving data set often have(Big-O)

Logarithmic O(log n)

What notation does code with a loop often have(Big-O)

Linear O(n)

What notation does code with a nested loop often have(Big-O)

Polynomial O(n^the number of loops)

What notation does code that is recursive often have(Big-O)

Exponential O(2^n)

Rank the time complexities

1. O(1)

2. O(log n)

3. O(n)

4. O(n²)

5. O(2^n)

What is the code for a Linear search

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

What is the time complexity of Linear search

O(n)

What are the 3 steps of a binary search

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.

What is the algorithm for binary search

What is the time complexity of binary search

O log n

What are the steps of a bubble sort algorithm?

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.

what is the algorithm for Bubble sort

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

What is the time complexity of bubble sort

O(n^2).

What are steps for an insertion sort?

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.

What is the algorithm for an insertion sort

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

What are the steps for a merge sort

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.

What is the time complexity for merge sort

O(n log²n)

What are the steps of quick sort?

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.

What is the time complexity for quicksort?

O(n²)

What are the steps for a depth first graph taversal?

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

What is the algorithm for a depth first traversal

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

What are the applications of depth first traversal

1. Finding a path between vertices

2. Solving puzzles such as mazes

3. Job scheduling

What are the steps of a breadth first traversal

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.

What are the applications of breadth first traversal

1. Finding the shortest patch between two points

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

What is the complexity of DFS and BFS

O(n²)