Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

OCR A-level Computer Science > 2.3 Algorithms > Flashcards

2.3 Algorithms Flashcards

1
Q

What are two things needed to be kept into mind when developing an algorithm?

A

-time complexity
-space complexity

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

Explain time complexities? What are they known as?

A

-how much time an algorithm requires to solve a particular problem
-known as big-o notation, shows the effectiveness of the algorithm
-shows the amount of time taken relative to the number of data elements given as an input

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

What is 0(1)?

A

-constant time complexity
-the amount of time taken to complete an algorithm is independent from the number of elements inputted

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

What is 0(n)?

A

-linear time complexity
-the amount of time taken to complete an algorithm is directly proportional to the number of elements inputted

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

What is 0(n^2)?

A

-polynomial time complexity
-the amount of time taken to complete an algorithm is directly proportional to the square of the elements inputted

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

What is 0(n^n)?

A

-polynomial time complexity
-the amount of time taken to complete an algorithm is directly proportional to the elements inputted to the power of n

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

What is 0(2^n)?

A

-exponential time complexity
-the amount of time taken to complete an algorithm will double with every additional item

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

What is 0(log n)?

A

-logarithmic time complexity
-the time taken to complete an algorithm will increase at a smaller rate as the number of elements inputted

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

What is 0(n log n)?

A

-logarithmic time complexity
-the time taken to complete an algorithm grows at a rate that is proportional to the number of elements inputted multiplied by the logarithm of n

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

What time complexity should be used for algorithms using a ‘divide and conquer approach’?

A

log n
n log n

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

What do we mean by space complexities? How can this be measured?

A

-the amount of storage the algorithm takes
-measured using big o-notation

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

What are the best/average/worst cases for time complexities for bubble sort? Why?

A

best- 0(n)
as this is when array is already sorted

average- 0(n^2)
as this is when elements are randomly ordered

worst- 0(n^2)
as this is when the elements are sorted in reverse order

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

What is the space complexity for bubble sort? Why?

A

0(1)
as it requires additional space for number of variables

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

What are the best/average/worst cases for time complexities for insertion sort? Why?

A

best- 0(n)
as this is when array is nearly sorted

average- 0(n^2)
as this is when array is randomly sorted

worst- 0(n^2)
as this is when array is sorted in reverse order

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

What is the space complexity for insertion sort? Why?

A

0(1)
as minimal extra space needed

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

What are the best/average/worst cases for time complexities for merge sort? Why?

A

all- 0(n log n)
as the algorithm is being decomposed
–> log n, due to the number of separations becomes n log n

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

What is the space complexity for merge sort? Why?

A

0(n)
as merge sort requires additional space for merging

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

What are the best/average/worst cases for time complexities for quick sort? Why?

A

best- 0(n log n)
as this is when the pivot consistently divides array in half and is balanced

average- 0(n log n)
as this is when the pivot consistently divides array in half and is balanced

worst- 0(n^2)
as this is when the pivot consistently results in unbalanced partitions

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

What is the space complexity for quick sort? Why?

A

0(log n)
as there is varying space depending on pivot and data

20
Q

What are the best/average/worst cases for time complexities for linear search? Why?

A

best- 0(1)
as this is when the target is at beginning of the list

average- 0(n)
as this is when the target can be randomly anywhere in the list, multiple iterations

worst- 0(n)
as this is when the target element is at the end of the list or not present

21
Q

What is the time complexity for linear search? Why?

A

0(1)
requires minimal space as nothing will be added or lost

22
Q

What are the best/average/worst cases for time complexities for binary search? Why?

A

best- 0(1)
as this is when the target is at the middle of the sorted list

average- 0(n log n)
as each comparison reduces the search space by 1/2

worst- 0(n log n)
as the target element could be at the beginning or end of the sorted list

23
Q

What is the space complexity for binary search? Why?

A

0(1)
no extra space needed

24
Q

What are the best/average/worst cases for time complexities for hash table search? Why?

A

best- 0(1)
when there are no collisions and the hash function distributes keys evenly

average- 0(1)
no collisions and a good hash function

worst- 0(n)
as this is when there are many collisions which leads to a linear search within the has table search

25
Q

What is the time complexity for a hash table search? Why?

A

0(n)
as additional space is required for the storage of collisions or key-value pairs

26
Q

What are the four sorting algorithms?

A

-bubble
-insertion
-merge
-quick

27
Q

Describe bubble sort

A

a sorting algorithm that repeatedly loops through the list comparing elements and swapping if they’re in the wrong order
passes through the list until sorted

28
Q

How does bubble sort work?

A

start from beginning of array
2. compare each pair of adjacent elements
3. if the elements are in the wrong order, swap them
4. repeat this process for each pair of adjacent elements in the array
5. after the first pass (passing through the whole array), repeat the whole process until a pass is made with no swaps

29
Q

When may using bubble sort be inefficient?

A

when there are large data sets

30
Q

Describe insertion sort

A

a sorting algorithm which places elements into a sorted sequence one element at a time

31
Q

How does insertion sort work?

A
  1. start with second element of the array
  2. compare the element with the one before it
  3. if the previous element is greater, swap them
  4. repeat this process until element is in its correct sorted position
  5. move to next unsorted element and repeat steps 2-4 until the entire array is sorted
32
Q

What is insertion sort useful for?

A

-efficient for small datasets
-good for nearly sorted data

33
Q

Describe merge sort

A

-a divide and conquer sorting algorithm
divides the unsorted list into ‘n’ sub-lists containing one element, then uses recursion repeatedly merging sub-lists to produce sorted sub-lists until the whole array is recombined

34
Q

How does merge sort work?

A

uses two functions: MergeSort and Merge
mergesort- divides
merge- combines

  1. divide the unsorted array until each element is by itself
  2. repeatedly merge each element ordering each element with every merge until list is fully combined
35
Q

What is merge sort useful for?

A

efficient for large data sets

36
Q

Describe quick sort

A

-a divide and conquer sorting algorithm
-works by selecting a ‘pivot’ element from the array and partitioning the other elements into two sub-arrays, according whether they are less than or greater than the pivot

37
Q

How does quick sort work?

A
  1. choose a pivot element from the array
  2. partition the array into two sub arrays: elements less than the pivot and the other greater
  3. process repeated recursively on each new sub array until all elements in the input are old pivots or form a list of 1 element
38
Q

What is quick sort useful for?

A

-efficient for large datasets
-pivot selection strategy influences performance

39
Q

What are the two searching algorithms?

A

-binary
-linear

40
Q

Describe binary search

A

an efficient sorting algorithm used to find the position of a target value within a sorted array or list

41
Q

How does binary search work?

A

only works on sorted data

  1. find the middle element
  2. compare elements on either side, unwanted half is discarded
  3. repeat process until desired element is found or if it doesn’t exist in data set
42
Q

Describe linear search

A

a searching algorithm which examines each element in a list or array one by one until the target value is found or the entire list is traversed

43
Q

How does linear search work?

A
  1. start from the first element in list
  2. compare current element with target value, if successful return the index, if not, repeat with next element
  3. repeat step two until target is found or the end of list is reached
44
Q

What is Dijkstra’s algorithm?

A

finds the shortest path between two nodes in a weighted graph

45
Q

What is A* algorithm?

A

a path-finding algorithm which adds on a heuristic value to improve efficiency of the process

OCR A-level Computer Science (8 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions