big o

Question 1

QUICK SORT

worst case time complexity?
worst case space complexity?

Answer 1

time - O(n^2)

space - O(log(n))

Question 2

MERGE SORT

worst case time complexity?
worst case space complexity?

Answer 2

time - O(n log(n))

space - O(n)

Question 3

BUBBLE SORT

worst case time complexity?
worst case space complexity?

Answer 3

time - O(n^2)

space - O(1)

Question 4

INSERTION SORT

worst case time complexity?
worst case space complexity?

Answer 4

time - O(n^2)

space - O(1)

Question 5

SELECTION SORT

worst case time complexity?
worst case space complexity?

Answer 5

time - O(n^2)

space - O(1)

Question 6

LINEAR SEARCH

worst case time complexity?

Answer 6

time - O(n)

Question 7

BINARY SEARCH

worst case time complexity?

Answer 7

time - O(log(n))

Question 8

what is the relationship between input size and execution time for O(1)?

Answer 8

always executes in the same time regardless of the size of the data set

Question 9

what is the relationship between input size and execution time for O(log(n))?

Answer 9

execution time increase is linear when input size is doubled

Question 10

what is the relationship between input size and execution time for O(n)?

Answer 10

execution time is proportional to the input size increase

Question 11

what is the relationship between input size and execution time for O(n^x)?

Answer 11

execution time increases relating to the highest degree of the polynomial complexity as the input size increases

Question 12

what is the relationship between input size and execution time for O(2^n)?

Answer 12

execution time increases exponentially as the input size increases

Question 13

what is the relationship between input size and execution time for O(n!)?

Answer 13

execution time increases in a factorial nature related to the input size

Question 14

what is the worst time complexity described by big O notation?

Answer 14

O(n!) or factorial time complexity

Question 15

what is the best time complexity described by big O notation?

Answer 15

O(1) or constant time complexity

Question 16

what feature of an algorithm commonly has O(log(n))?

Answer 16

divide and conquer / halving the input size with every pass

Question 17

what feature of an algorithm commonly has O(n)?

Answer 17

iterating through the size of the input

Question 18

what feature of an algorithm commonly has O(n^x)?

Answer 18

nested loops, each loop relating to the input size

Question 19

what feature of an algorithm commonly has O(2^n)?

Answer 19

recursive functions

Question 20

what feature of an algorithm commonly has O(n!)?

Answer 20

trial and error / guessing until a condition is met

Question 21

what is the domain of an algorithm?

Answer 21

all possible inputs into the algorithm

Question 22

what is the codomain of an algorithm?

Answer 22

all possible outputs of an algorithm

Question 23

what is the range of an algorithm?

Answer 23

all of the actual outputs of an algorithm