2
$\begingroup$

I just learnt decision tree concept in class. I have a question for homework. It says to prove that for searching an element in n*n matrix the lower bound is logn and prove it using decision tree.

My question here is using comparison based model, how can we have the lower bound as log n. what if the matrix is unsorted?

|cite|improve this question
$\endgroup$
  • $\begingroup$ If the matrix is unsorted, in the worst case you'll have to scan all elements, so the complexity would be $n^2$. Try to think of a proof. $\endgroup$ – Yuval Filmus Sep 10 at 20:14
  • $\begingroup$ try to compare it to searching in a sorted array. What are the changes in the bounds? it might help to remember the basic arithmetic operations on logarithms ($\log a^2 = 2 \log a) $\endgroup$ – narek Bojikian Sep 10 at 21:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.