WGU C949 EXAM 4 QUESTIONS AND
CORRECT ANSWERS!!
What is the time complexity of:
for i in range(n):
for j in range(i):
print(i, j)
O(n^2) - though not full nn, it's still quadratic because the total number of inner iterations is
(n(n-1))/2
What Big-O notation is Exponential?
O(2^n)
What Big-O notation is Factorial?
O(n!)
What is the time complexity of this loop?
for i in range (n):
print(i)
O(n) - runs once per item
What is the time complexity of this nested loop?
for i in range(n):
for j in range(n):
print(i, j)
O(n^2) - each inner loop runs n times for every outer loop
What is the complexity of this loop?
i=1
while i < n:
, i *= 2
O(log n) - doubles each time (log base 2)
If an algorithm reduces the problem size by half each time, what's the time complexity?
O(log n) - typical of binary search or divide-and-conquer algorithms
What is the Big-O of accessing an element in a Hash table (average case)?
O(1) - constant time lookup
What is the Big-O of accessing an element in a linked list?
O(n) - must traverse nodes
What is the Big-O of inserting into the end of an array (amortized)?
O(1) - unless resizing is needed, which is O(n) occasionally
What is the Big-O of inserting at the beginning of an Array?
O(n) - all elements must be shifted
What is the amortized time complexity of appending to a dynamic array?
O(1) - resizing costs O(n)
What causes a dynamic array to resize?
When its capacity is full - usually doubles in size
What is the worst-case time complexity of appending to a full dynamic array?
O(n) - due to copying all elements to a new array
True or False: O(n + log n) simplifies to O(n)
True
True or False: O(n) + O(n^2) simplifies to O(n^2)
True
True or False: O(n) * O(log n) is O(n log n)
CORRECT ANSWERS!!
What is the time complexity of:
for i in range(n):
for j in range(i):
print(i, j)
O(n^2) - though not full nn, it's still quadratic because the total number of inner iterations is
(n(n-1))/2
What Big-O notation is Exponential?
O(2^n)
What Big-O notation is Factorial?
O(n!)
What is the time complexity of this loop?
for i in range (n):
print(i)
O(n) - runs once per item
What is the time complexity of this nested loop?
for i in range(n):
for j in range(n):
print(i, j)
O(n^2) - each inner loop runs n times for every outer loop
What is the complexity of this loop?
i=1
while i < n:
, i *= 2
O(log n) - doubles each time (log base 2)
If an algorithm reduces the problem size by half each time, what's the time complexity?
O(log n) - typical of binary search or divide-and-conquer algorithms
What is the Big-O of accessing an element in a Hash table (average case)?
O(1) - constant time lookup
What is the Big-O of accessing an element in a linked list?
O(n) - must traverse nodes
What is the Big-O of inserting into the end of an array (amortized)?
O(1) - unless resizing is needed, which is O(n) occasionally
What is the Big-O of inserting at the beginning of an Array?
O(n) - all elements must be shifted
What is the amortized time complexity of appending to a dynamic array?
O(1) - resizing costs O(n)
What causes a dynamic array to resize?
When its capacity is full - usually doubles in size
What is the worst-case time complexity of appending to a full dynamic array?
O(n) - due to copying all elements to a new array
True or False: O(n + log n) simplifies to O(n)
True
True or False: O(n) + O(n^2) simplifies to O(n^2)
True
True or False: O(n) * O(log n) is O(n log n)
