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?