@toxicdesire
"Θ(f(n)) seems to be most accurate answer, but it's not an option. If Θ(f(n)) is the correct answer, does that not mean both O(f(n)) and Ω(f(n)) are equally relevant?"
yes, For example, in case of "sorting" problem, Heap Sort and Merge-Sort are asymptotically optimal comparison sorts which is given as corollary above because in worst case, $O(nlgn)$ and $\Omega(nlogn)$ matches which implies $\Theta(nlgn)$. So, we can say "best" algorithm for comparison based sorting is merge and heap sorts whose running time is represented by $\Theta(nlgn).$ So, here Theta,Big Omege, Big Theta all says that we found the best algorithm for sorting which work for all inputs.
"Now, let's say there's a problem A. Now, let's assume lower bound to the problem A is Ω(n⋅logn). Now assume the problem can be solved with two algorithms, both have Ω(n⋅logn) as lower bounds. Tell me which one is the best one? "
suppose, you have proved same lower bound for "no. of comparisons" by both algorithms then I will check how much memory will be taken by both algorithms and other parameters and then say which is optimal.
"What gives Ω(f(n)) an edge over O(f(n)) for choosing a best algorithm to a problem?"
Ω(f(n)) gives lower bound means can we do better than something or not. For example, we can't sort numbers or anything with less than nlgn comparisons (or) we can't do better than nlgn. Lower bounds are harder to prove.
