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!

  • 1
    $\begingroup$ 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. $\endgroup$ – Yuval Filmus Aug 28 '18 at 18:21
  • 1
    $\begingroup$ 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}$). $\endgroup$ – Yuval Filmus Aug 29 '18 at 6:52

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.