CSE 310 EXAM 1 QUESTIONS AND ANSWERS 100% PASS

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.