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 acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.