Computer Science - Algorithms

studied byStudied by 34 people
5.0(1)
Get a hint
Hint

What is the Big-O Notation

1 / 32

flashcard set

Earn XP

33 Terms

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

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

  2. 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

  1. O(1)

  2. O(log n)

  3. O(n)

  4. O(n²)

  5. 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

  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.

New cards
17

What is the algorithm for binary search

<p></p>
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:

  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.

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:

  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.

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:

  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.

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:

  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.

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:

  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

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

  1. Finding a path between vertices

  2. Solving puzzles such as mazes

  3. Job scheduling

New cards
31

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.

New cards
32

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

New cards
33

What is the complexity of DFS and BFS

O(n²)

New cards

Explore top notes

note Note
studied byStudied by 4 people
... ago
5.0(1)
note Note
studied byStudied by 94 people
... ago
5.0(1)
note Note
studied byStudied by 433 people
... ago
5.0(3)
note Note
studied byStudied by 33 people
... ago
5.0(1)
note Note
studied byStudied by 28 people
... ago
5.0(1)
note Note
studied byStudied by 32 people
... ago
5.0(2)
note Note
studied byStudied by 11 people
... ago
5.0(1)
note Note
studied byStudied by 29 people
... ago
5.0(1)

Explore top flashcards

flashcards Flashcard (121)
studied byStudied by 2 people
... ago
5.0(1)
flashcards Flashcard (84)
studied byStudied by 13 people
... ago
5.0(1)
flashcards Flashcard (20)
studied byStudied by 16 people
... ago
5.0(1)
flashcards Flashcard (27)
studied byStudied by 8 people
... ago
5.0(1)
flashcards Flashcard (83)
studied byStudied by 12 people
... ago
5.0(1)
flashcards Flashcard (53)
studied byStudied by 2 people
... ago
5.0(1)
flashcards Flashcard (48)
studied byStudied by 50 people
... ago
5.0(1)
flashcards Flashcard (24)
studied byStudied by 16 people
... ago
5.0(1)
robot