Studied by 29 people

5.0(1)

get a hint

hint

1

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.

New cards

2

How is a linear function expressed?

f(x) = ax+ c

New cards

3

How is a polynomial function expressed?

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

New cards

4

How is an exponential function expressed?

f(x) = ab^x

New cards

5

How is a logarithmic function expressed?

f(x) = a logn x

New cards

6

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

Remove all terms except the one with the largest factor

Remove any constants

New cards

7

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

O(n)

New cards

8

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

A constant complexity O(1)

New cards

9

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

Logarithmic O(log n)

New cards

10

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

Linear O(n)

New cards

11

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

Polynomial O(n^the number of loops)

New cards

12

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

Exponential O(2^n)

New cards

13

Rank the time complexities

O(1)

O(log n)

O(n)

O(n²)

O(2^n)

New cards

14

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

New cards

15

What is the time complexity of Linear search

O(n)

New cards

16

What are the 3 steps of a binary search

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

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

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

New cards

17

What is the algorithm for binary search

New cards

18

What is the time complexity of binary search

O log n

New cards

19

What are the steps of a bubble sort algorithm?

The steps of a bubble sort algorithm are as follows:

Start with an unsorted list of elements.

Compare adjacent elements in the list.

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

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

Continue this process for each element in the list.

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

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

New cards

20

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

New cards

21

What is the time complexity of bubble sort

O(n^2).

New cards

22

What are steps for an insertion sort?

The steps for an insertion sort are as follows:

Start with the second element in the list.

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

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

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

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.

New cards

23

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

New cards

24

What are the steps for a merge sort

The steps for a merge sort algorithm are as follows:

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

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.

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.

New cards

25

What is the time complexity for merge sort

O(n log²n)

New cards

26

What are the steps of quick sort?

The steps of the Quick Sort algorithm are as follows:

Choose a pivot element from the array.

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

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

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.

New cards

27

What is the time complexity for quicksort?

O(n²)

New cards

28

What are the steps for a depth first graph taversal?

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

Choose a starting vertex.

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

Add the neighbour to the visited list

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

Repeat steps 2-4

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

New cards

29

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

New cards

30

What are the applications of depth first traversal

Finding a path between vertices

Solving puzzles such as mazes

Job scheduling

New cards

31

What are the steps of a breadth first traversal

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

Start by visiting the root node.

Enqueue the root node.

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.

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.

New cards

32

What are the applications of breadth first traversal

Finding the shortest patch between two points

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

New cards

33

What is the complexity of DFS and BFS

O(n²)

New cards