# Decision Tree for searching an element in an n*n matrix

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?

• 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. – Yuval Filmus Sep 10 '19 at 20:14
• 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) – narek Bojikian Sep 10 '19 at 21:35