Big O Notation

Question 1

What is the order from the best O time complexities to the worst ones?

Answer 1

O(1), O(log n), O(sqrt n), O(n), O(n log n), O(n^2), O(2^n), O(n!)

Question 2

How does O(1) work?

Answer 2

• Same time returned regardless of input size

Question 3

How does O(n) work?

Answer 3

• Uses entire input size once

Question 4

How does O(log n) work?

Answer 4

• Runtime depends on half the input size
• Continues to somewhat halve

Question 5

How does O(n^2) work?

Answer 5

• Nested loops

Question 6

How do you determine the O value of two independent methods?

Answer 6

O(a + b)

Question 7

How do you determine the O value of nested loops?

Answer 7

O(a * b)

Question 8

What are the time complexities of binary search?

Answer 8

Best: O(1)
Other: O(log n)

Question 9

What are the space complexities for all the sorting/searching methods?

Answer 9

• O(1): both bubbles, selection, insertion,
• O(log n): quick sort
• O(n): merge sort

Question 10

What are the time complexities of bubble sort?

Answer 10

O(n^2) for all

Question 11

What are the time complexities of optimized bubble sort?

Answer 11

Best: O(n)
Others: O(n^2)

Question 12

What are the time complexities for selection sort?

Answer 12

O(n^2) for all

Question 13

What are the time complexities for insertion sort?

Answer 13

Best: O(n)
Others: O(n^2)

Question 14

What time complexity does String.substring() give?

Answer 14

O(n)

Question 15

What time complexity does String.indexOf() give?

Answer 15

O(n)

Question 16

What time complexity does ArrayList.remove(i) give?

Answer 16

O(n)

Question 17

What time complexity does String.add(i, val) give?

Answer 17

O(n)

Question 18

What time complexity does String.get(i) give?

Answer 18

O(1)

Question 19

What time complexity does a nested loop that shrinks give? What can shrink?

Answer 19

O(n^2)
- y can have j < i or j < n

Question 20

What does binary recursion give off?

Answer 20

O(2^n)

Question 21

When you include the use of strings in a loop, what is the time complexity given?

Answer 21

O(n^2)

Question 22

How do insertion and selection sort compare on an array that is mostly sorted?

Answer 22

• insertion sort goes through less comparisons and shifts overall
• selection sort compares every index every pass

Question 23

How do insertion sort, bubble sort, and selection sort compare in space usage?

Answer 23

All are the same