2.3.2. Algorithms for the Main Data Structures

Question 1

What 2 pieces of informations allow you to analyse an algorithm?

Answer 1

1. time complexity 2. space complexity

Question 2

What is meant by the time complexity of an algorithm?

Answer 2

the amount of time required to solve a particular problem

Question 3

What is the notation for time complexity?

Answer 3

big-O-notation

Question 4

What does big-O notation show?

Answer 4

the effectiveness of an algorithm

Question 5

What is big-O notation good for?

Answer 5

predicting the amount of time taken to solve an algorithm given the number of items input

Question 6

What does a linear time complexity mean?

Answer 6

the amount of time taken to complete an algorithm algorithm is directly proportional to the number of items input

Question 7

What does a constant time complexity mean?

Answer 7

the amount of time taken to complete an algorithm is independent of the number of items input

Question 8

What does a polynomial time complexity mean?

Answer 8

the amount of time taken to complete an algorithm is proportional to the number of items input, to the power of n

Question 9

What does an exponential time complexity mean?

Answer 9

the amount of time taken to complete an algorithm is proportional to 2 to the power of the number of items input

Question 10

What does a logarithmic time complexity mean?

Answer 10

the amount of time taken to complete an algorithm will increase at a smaller rate as the number of items input increases

Question 11

What is a logarithm?

Answer 11

how many times a certain number (base) is multiplied by itself to reach another number

Question 12

What is space complexity?

Answer 12

the amount of storage an algorithm takes up

Question 13

What is an algorithm?

Answer 13

a series of steps that complete a task

Question 14

How do you reduce the space complexity?

Answer 14

complete all operations on a single data set

Question 15

How do you reduce the time complexity of an algorithm? (2 steps)

Answer 15

1. reduce the amount for loops 2. reduce the amount of items, operations are completed on

Question 16

What is the big-O notation of a linear search algorithm?

Answer 16

O(n)

Question 17

What is the big-O notation of binary search algorithm?

Answer 17

O(log(n))

Question 18

What is the big-O notation of a bubble sort algorithm?

Answer 18

O(n2)