Big-O

Question 1

What is known as Constant complexity?

Answer 1

1

Question 2

What is known as Logarithmic complexity?

Answer 2

log(n)

Question 3

What is known as Squared Logarithmic complexity?

Answer 3

[log(n)]^2

Question 4

What is known as Fractional Polynomial complexity?

Answer 4

n^c [where 0<c<1]

Question 5

What is known as Linear complexity?

Answer 5

n

Question 6

What is known as Linearithmic complexity?

Answer 6

n log(n)

Question 7

What is known as Quadratic complexity?

Answer 7

n^2

Question 8

What is known as Exponential complexity?

Answer 8

2^n

Question 9

What is known as Factorial complexity?

Answer 9

n!

Question 10

What is the smallest complexity?

Answer 10

Constant, O(1)

Question 11

What is the largest COMMON complexity?

Answer 11

Factorial, O(n!)

Question 12

Which is larger:
n^2 or log(n)

Answer 12

n^2

Question 13

Which is larger:
k^n (where k>3) or n^[log(log(n))]

Answer 13

k^n (where k>3)

Question 14

Which is larger:
n^n or n!

Answer 14

n^n

Question 15

Which is larger:
n log(n) or log(n!)

Answer 15

n log(n)

Question 16

Which is larger:
n^2^n or 2^n^2

Answer 16

n^2^n

Question 17

Which is larger:
2^n or 2^2n

Answer 17

2^2n

Question 18

Which is larger:
[log(n)]^2 or n^k (where k>3)

Answer 18

n^k (where k>3)

Question 19

Which is larger:
n^c (where 0<c<1) n^2

Answer 19

n^2

Question 20

Which is larger:
2^n^2 or n^n

Answer 20

n^n

Question 21

Which is larger:
2^n or n!

Answer 21

n!

Question 22

What is the Big-O of this code snippet, and how many times is PCO run?

for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
for (int k = 0; k< n; k++) {
PCO } } }

Answer 22

PCO = n * n * n = n^3
O(n^3)

Question 23

What is the Big-O of this code snippet, and how many times is PCO run?

for (int i = 0; i < n; i++) {
for (int k = 0; k < n; j++) { PCO }
for (int k = 0; k< n; k++) { PCO }
}

Answer 23

PCO = n * (n + n) = 2n^2
O(n^2)

Question 24

What is the Big-O of this code snippet, and how many times is PCO run?

for (int i = 0; i < n; i++) { PCO }

Answer 24

PCO = n
O(n)

Question 25

# What is the Big-O of this code snippet, and how many times is PCO run? for (int i = 1; i <= n; i++) { PCO }

Answer 25

PCO = n O(n)

Question 26

# What is the Big-O of this code snippet, and how many times is PCO run? for (int i = 1; i < n; i++) { PCO }

Answer 26

PCO = n - 1 O(n)

Question 27

# What is the Big-O of this code snippet, and how many times is PCO run? for (int i = 0; i < A; i++) { PCO } | When A is an Integer

Answer 27

PCO = A O(1)

Question 28

# What is the Big-O of this code snippet, and how many times is PCO run? for (int i = 1; i <= A; i++) { PCO } | Where A is an Integer

Answer 28

PCO = A O(1)

Question 29

# What is the Big-O of this code snippet, and how many times is PCO run? for (int i = 1; i < A; i++) { PCO } | Where A is an Integer

Answer 29

PCO = A - 1 O(1)

Question 30

# What is the Big-O of this code snippet, and how many times is PCO run? for (int i = A; i > 0; i- -) { PCO } | Where A is an Integer

Answer 30

PCO = A O(1)

Question 31

# What is the Big-O of this code snippet, and how many times is PCO run? for (int i = 1; i <= n; i++) { for (int j = 1; j <= i; j++) {PCO } } | Why is that?

Answer 31

PCO = 1 + 2 + ... + n = n(n+1)/2 O(n^2) i is 1, j runs once i is 2, j runs twice i is n, j runs n times | Sum of 1 -> n

Question 32

# What is the Big-O of this code snippet, and how many times is PCO run? Sequence i: 1, 3, 5, ..., n N IS EVEN for (int i = 1; i <= n; i++) { PCO } | Why is that? Identify the sequence

Answer 32

Arithmetic sequence: First value is 1, Last value is n-1 (last odd before even n), Difference of adjacent values is 2 PCO = [Last - First]/Diff + 1 = [n - 1 - 1]/2 + 1 = n/2 O(n)

Question 33

# What is the Big-O of this code snippet, and how many times is PCO run? Sequence i: 1, 3, 5, ..., n N IS ODD for (int i = 1; i <= n; i++) { PCO } | Why is that? Identify the sequence

Answer 33

Arithmetic sequence: First value is 1, Last value is n (n is odd), Difference of adjacent values is 2 PCO = [Last - First]/Diff + 1 = [n - 1]/2 + 1 = [n + 1]/2 O(n)

Question 34

What can 9^n be simplified to?

Answer 34

k^n (where k > 3)

Question 35

What can (n-3)! be simplified to?

Answer 35

n!

Question 36

What can ln^3(n) be simplified to?

Answer 36

[log(n)]^3

Question 37

What can 0.0008n^2 + 1000n^2log(n) + 1 be simplified to?

Answer 37

n^2logn

Question 38

What can 2^3n be simplified to?

Answer 38

2^3n

Question 39

What can root_3(n) be simplified to?

Answer 39

n^c (where 0 < c < 1)

Question 40

What can 100000n^2 be simplified to?

Answer 40

n^2

Question 41

What can 5log(n + 100)^1000 be simplified to?

Answer 41

log(n)^1000

Question 42

Which is larger: nlog(n) or n^2log(n)

Answer 42

n^2log(n)

Question 43

Which is larger: n^2 or n^2log(n)

Answer 43

n^2log(n)

Question 44

Which is larger: log(n) or ln(n)

Answer 44

Neither, they are functionally the same

Question 45

What should be the order of: A) 9^n B) (n-3)! C) ln^3(n) D) 0.0008n^2 + 1000n^2log(n) + 1 E) 2^3n F) root_3(n) G) 100000n^2 H) 5log(n+100)^1000

Answer 45

C < H < F < G < D < E < A < B

Question 46

The implementation of an algorithm with input n where n is a power of 2. EXACTLY how many times is PCO run? for(int i = n; i > 0; i = i>>1) { for(int j = 0; j < i; j++) { for(int k = 8; k > 1; k- -) {PCO} } }

Answer 46

A is run log_2(n) + 1 times B is run i times C is run 8 times PCO = The sum of i * 7 where i = n, n/2, n/4 ... 1 = 7 * Geometric Series = 7 * The sum from k=0 to log_2(n) of n/2^k = 7(n + n/2 + n/4 + 1) = 7(2n-1) = 14n-7 = O(n)