I am doing a computer science assignment.
In the assignment, I was asked to find an algorithm with time complexity $O(|E|)$. The input is a connected acyclic graph (a free tree). I have come up with an algorithm costs $O(V^2)$.
I am thinking of whether the time complexity of my algorithm satisfy the requirement or not. Because I know that in a complete graph, $E = O(V^2)$. However, in this question, I am dealing with a tree with $V-1$ edges. So the question is which of the following is true in a tree: $E=O(V^2)$ or $E=O(V)$?
It is not. As you said $|E| = |V| - 1$ here. Hence, if your algorithm is in $O(|V|^2)$ it is not satisfied $O(|E|)$ here.