WGU C960 Discrete Mathematics II
Full Objective Assessment Practice Questions and Answers
1) Big-O Basics
Question 1:
Determine the Big-O classification of the function
[
f(n)=7n^3+4n^2+100n+9
]
Answer:
[
O(n^3)
]
Explanation:
In Big-O notation, only the highest-order term matters for large values of (n). The lower-degree
terms (4n^2), (100n), and the constant 9 become insignificant compared with (7n^3). Constants
are ignored as well, so the growth rate is (O(n^3)).
2) Comparing Growth Rates
Question 2:
Arrange the following functions from slowest-growing to fastest-growing:
[
\log n,\quad n,\quad n\log n,\quad n^2,\quad 2^n
]
Answer:
[
\log n,\quad n,\quad n\log n,\quad n^2,\quad 2^n
]
Explanation:
A logarithmic function grows more slowly than a linear function. Linear grows more slowly than
linearithmic (n\log n), which grows more slowly than quadratic (n^2). Exponential (2^n) grows
the fastest of all listed functions.
,3) Nested Loops
Question 3:
Analyze the time complexity of the following pseudocode:
count = 0
for i = 1 to n
for j = 1 to n
count = count + 1
Answer:
[
O(n^2)
]
Explanation:
The outer loop executes (n) times. For each iteration of the outer loop, the inner loop also
executes (n) times. Therefore, the total number of operations is (n \cdot n = n^2). Hence the
running time is (O(n^2)).
4) Triangular Loop Count
Question 4:
Find the time complexity of the following pseudocode:
for i = 1 to n
for j = 1 to i
print(i, j)
Answer:
[
O(n^2)
]
Explanation:
The total number of inner loop iterations is:
[
1+2+3+\cdots+n=\frac{n(n+1)}{2}
]
That expression is quadratic in (n), so the complexity is (O(n^2)).
, 5) Logarithmic Loop
Question 5:
What is the time complexity of the following algorithm?
i = 1
while i < n
i = 2i
Answer:
[
O(\log n)
]
Explanation:
Each iteration doubles the value of (i). The number of doublings needed to reach (n) is
approximately (\log_2 n). Therefore, the time complexity is (O(\log n)).
6) Recurrence Relation
Question 6:
Solve the recurrence:
[
T(n)=T(n-1)+5,\quad T(1)=2
]
Answer:
[
T(n)=5n-3
]
Explanation:
Expand the recurrence:
[
T(n)=T(n-1)+5
]
[
T(n-1)=T(n-2)+5
]
Full Objective Assessment Practice Questions and Answers
1) Big-O Basics
Question 1:
Determine the Big-O classification of the function
[
f(n)=7n^3+4n^2+100n+9
]
Answer:
[
O(n^3)
]
Explanation:
In Big-O notation, only the highest-order term matters for large values of (n). The lower-degree
terms (4n^2), (100n), and the constant 9 become insignificant compared with (7n^3). Constants
are ignored as well, so the growth rate is (O(n^3)).
2) Comparing Growth Rates
Question 2:
Arrange the following functions from slowest-growing to fastest-growing:
[
\log n,\quad n,\quad n\log n,\quad n^2,\quad 2^n
]
Answer:
[
\log n,\quad n,\quad n\log n,\quad n^2,\quad 2^n
]
Explanation:
A logarithmic function grows more slowly than a linear function. Linear grows more slowly than
linearithmic (n\log n), which grows more slowly than quadratic (n^2). Exponential (2^n) grows
the fastest of all listed functions.
,3) Nested Loops
Question 3:
Analyze the time complexity of the following pseudocode:
count = 0
for i = 1 to n
for j = 1 to n
count = count + 1
Answer:
[
O(n^2)
]
Explanation:
The outer loop executes (n) times. For each iteration of the outer loop, the inner loop also
executes (n) times. Therefore, the total number of operations is (n \cdot n = n^2). Hence the
running time is (O(n^2)).
4) Triangular Loop Count
Question 4:
Find the time complexity of the following pseudocode:
for i = 1 to n
for j = 1 to i
print(i, j)
Answer:
[
O(n^2)
]
Explanation:
The total number of inner loop iterations is:
[
1+2+3+\cdots+n=\frac{n(n+1)}{2}
]
That expression is quadratic in (n), so the complexity is (O(n^2)).
, 5) Logarithmic Loop
Question 5:
What is the time complexity of the following algorithm?
i = 1
while i < n
i = 2i
Answer:
[
O(\log n)
]
Explanation:
Each iteration doubles the value of (i). The number of doublings needed to reach (n) is
approximately (\log_2 n). Therefore, the time complexity is (O(\log n)).
6) Recurrence Relation
Question 6:
Solve the recurrence:
[
T(n)=T(n-1)+5,\quad T(1)=2
]
Answer:
[
T(n)=5n-3
]
Explanation:
Expand the recurrence:
[
T(n)=T(n-1)+5
]
[
T(n-1)=T(n-2)+5
]
