CSE 310 EXAM 1 QUESTIONS AND
ANSWERS 100% PASS
Big O notation - ANS O(g(n) = f(n) if f(n) <= a*g(n) while n >= b
Big Ω notation - ANS Ω(g(n)) = f(n) if f(n) >= a*g(n) while n >= b
Big Θ notation - ANS Θ(g(n)) = f(n) if f(n) <= a*g(n) and f(n) >= b*g(n) for all n >= c
To prove correctness of algorithm, show ______, _____ and _____ hold - ANS initialization,
maintenance, and termination
Index of left child of node - ANS i = index of node
2*i = index of node's left child
parent index in heap - ANS i = index of node
floor(i/2) = index of node's parent
What does heap-extract max do? - ANS 1) takes out the head of heap and replaces it with last
node
2) performs max-heapify on head
1 @COPYRIGHT 2025/2026 ALLRIGHTS RESERVED.
, Find the expression associated with the runtime of this pseudocode (i.e. C1 x n + C2 x n ... etc)
and find the big O approximation
k=1 // C1
do // C2
{
j = 1 // C3
do // C4
{
j = j*2 // C5
}while(j < n) // C6
k++ // C7
}while (k < n) // C8 - ANS C1 x 1 + C2 x n + C3 x n + C4 x n(log_2(n)) + C5 x n(log_2(n)) + C6 x
n(log_2(n)) + C7 x n + C8 x n = O(nlogn)
Time of max-heapify - ANS O(logn)
O approximation of T(n) = T(n/2)+cn+b - ANS O(nlogn)
What is the height of a heap? - ANS The number of edges from head to lowest node
Quicksort best case (and what causes it?) - ANS O(nlogn) when the pivot perfectly divides the
array each iteration
Heap-increase-key runtime - ANS O(logn)
2 @COPYRIGHT 2025/2026 ALLRIGHTS RESERVED.
ANSWERS 100% PASS
Big O notation - ANS O(g(n) = f(n) if f(n) <= a*g(n) while n >= b
Big Ω notation - ANS Ω(g(n)) = f(n) if f(n) >= a*g(n) while n >= b
Big Θ notation - ANS Θ(g(n)) = f(n) if f(n) <= a*g(n) and f(n) >= b*g(n) for all n >= c
To prove correctness of algorithm, show ______, _____ and _____ hold - ANS initialization,
maintenance, and termination
Index of left child of node - ANS i = index of node
2*i = index of node's left child
parent index in heap - ANS i = index of node
floor(i/2) = index of node's parent
What does heap-extract max do? - ANS 1) takes out the head of heap and replaces it with last
node
2) performs max-heapify on head
1 @COPYRIGHT 2025/2026 ALLRIGHTS RESERVED.
, Find the expression associated with the runtime of this pseudocode (i.e. C1 x n + C2 x n ... etc)
and find the big O approximation
k=1 // C1
do // C2
{
j = 1 // C3
do // C4
{
j = j*2 // C5
}while(j < n) // C6
k++ // C7
}while (k < n) // C8 - ANS C1 x 1 + C2 x n + C3 x n + C4 x n(log_2(n)) + C5 x n(log_2(n)) + C6 x
n(log_2(n)) + C7 x n + C8 x n = O(nlogn)
Time of max-heapify - ANS O(logn)
O approximation of T(n) = T(n/2)+cn+b - ANS O(nlogn)
What is the height of a heap? - ANS The number of edges from head to lowest node
Quicksort best case (and what causes it?) - ANS O(nlogn) when the pivot perfectly divides the
array each iteration
Heap-increase-key runtime - ANS O(logn)
2 @COPYRIGHT 2025/2026 ALLRIGHTS RESERVED.
