# Prove lower bound of searching algorithm on Young Tableau

I want to prove the search of an element in a Young tableau of size $n\times n$ is $\Omega(n)$, but I do not have any clue. Any help is appreciated!

• I think some information is missing here. Searching an element in a Young tableau takes $\Omega(n^2)$ queries. I'm assuming you're looking at a standard Young tableau. It would be a good idea to state your problem without mentioning the term Young tableau. – Yuval Filmus Aug 28 '18 at 18:21
• Try embedding an unordered list of length $n$ in the secondary diagonal of your tableau (i.e. the one going from $x_{1n}$ to $x_{n1}$). – Yuval Filmus Aug 29 '18 at 6:52