Exercise: Suggest an effective algorithm finding Hamiltonian path in tournament with $n$ vertices using adjacency matrix T[1..n, 1..n].
Firstly, I proved that such path always exists. It was an easy induction, we can construct such path adding consecutive vertices to it, because each vertex can be added before first vertex in current path or after the last vertex or in other case, for this vertex (j) there exist vertices (i) and (i+1) such that T[ (i), (j) ]=true and T[ (j), (i+1) ]=true, so it can be added between vertices (i) and (i+1).
Basing on this algorithm it is easy to solve this problem in $O(n^2)$. Is it effective?
Because the second part of this exercise is to prove that every algorithm that finds Hamiltonian path in $n$-tournament given by adjacency matrix T[1..n, 1..n] does it in at least $\Omega(n \log n)$ operations of checking matrix T.
I completely don't know how to approach this problem, it seems very hard to prove something for every algorithm (that uses adjacency matrix).