G is an unweighted, undirected graph. Then, I cannot prove that [deciding whether G has a path of length greater than k] is NP-Complete.
How can I show whether the algorithm is NP-complete or not?
Let $G$ be your graph, and let it have $n$ vertices.
The Hamiltonian path problem is NP-complete. $G$ has a Hamiltionian path if and only if its longest path has length $n - 1$. Thus, the decision problem you described must be NP-complete.
This problem can be shown to NP-hard by reducing the longest path problem to it. It's not hard to do so maybe you want to give it a try first before I give you the reduction.