CSE 331 Exam 1 ACTUAL UPDATED QUESTIONS AND CORRECT ANSWERS
Big O "f(n) is less than or equal to another function g(n)". Upper bound on growth rate.
f(n) is O(g(n)) means that the growth rate of f(n) is no more than that of g(n)
Big Omega a function grows at a rate that is "greater than or equal to that of another function"
Big Theta allows us to say that 2 function grow at the same rate. f(n) is O(g(n)) and f(n) is
Big_Omega(g(n))
, 1/j is equal to O of what O(logn)
3 way disjoint sets, how to make better after the first 2 loops, if the values are not equal theres no point in entering the
third loop, making this O(n^2) not O(n^3)
big O of fibonacci number sequence O(2^n)
run time of insertion sort O(n^2)
little-oh notation f(n) is less than but not equal to o(g(n))
little-omega(w) f(n) is greater but not equal to g(n)
reflectivity property of time complexities f(n) = big_theta(f(n))
symmetry property of time complexities f(n) = big_theta(g(n)) if and only if g(n) = big_theta(f(n))
Transpose property of time complexities f(n) = O(g(n)) ----- > g(n) = big_omega(f(n))
run time of merge sort O(nlogn)
run time of merging 2 sorted lists in merge sort O(n) - for doubly linked list
height of merge sort tree O(logn)
worst/best case of merge sort NONE, always O(nlogn)
how to divide into 2 lists for merge sort n//2 where n is the size of the OG list
O(n^2) sorting algorithms insertion sort, bubble sort
all sorting algorithms are big omega of... big_omega(n), must search all elements at least once
run time of selection sort O(n^2)
merge sort recursion function T(n) = 2T(n/2)+n
T(1) = 1 if n<2
Big O "f(n) is less than or equal to another function g(n)". Upper bound on growth rate.
f(n) is O(g(n)) means that the growth rate of f(n) is no more than that of g(n)
Big Omega a function grows at a rate that is "greater than or equal to that of another function"
Big Theta allows us to say that 2 function grow at the same rate. f(n) is O(g(n)) and f(n) is
Big_Omega(g(n))
, 1/j is equal to O of what O(logn)
3 way disjoint sets, how to make better after the first 2 loops, if the values are not equal theres no point in entering the
third loop, making this O(n^2) not O(n^3)
big O of fibonacci number sequence O(2^n)
run time of insertion sort O(n^2)
little-oh notation f(n) is less than but not equal to o(g(n))
little-omega(w) f(n) is greater but not equal to g(n)
reflectivity property of time complexities f(n) = big_theta(f(n))
symmetry property of time complexities f(n) = big_theta(g(n)) if and only if g(n) = big_theta(f(n))
Transpose property of time complexities f(n) = O(g(n)) ----- > g(n) = big_omega(f(n))
run time of merge sort O(nlogn)
run time of merging 2 sorted lists in merge sort O(n) - for doubly linked list
height of merge sort tree O(logn)
worst/best case of merge sort NONE, always O(nlogn)
how to divide into 2 lists for merge sort n//2 where n is the size of the OG list
O(n^2) sorting algorithms insertion sort, bubble sort
all sorting algorithms are big omega of... big_omega(n), must search all elements at least once
run time of selection sort O(n^2)
merge sort recursion function T(n) = 2T(n/2)+n
T(1) = 1 if n<2
