Date: 09 Mar 2014 13:24
Number of posts: 8
RSS: New posts
Just to make sure we are using the same definitions - these are the definitions used in this course.:
A cycle by definition can't have repeating edges.
A simple cycle doesn't have repeating vertices.
You can find any cycle you like, even a non-simple cycle. I don't see how it makes the question easier, as it is very easy to find a simple cycle given a non-simple cycle.
In one of the lessons (videotaped lessons), we were told not to try to define n as a function of m or vice versa in order to simplify the complexity. Is this just when looking at the WC scenario? Can we simplify the complexity for certain cases in this question? otherwise, I get the same complexity for both a and b.
What was said in the lessons is always true. For example, take BFS - it's running time is $O(|V|+|E|)$. But $|E| = |V|^2$, so you could state the running time as $O(|V|^2)$, which is correct, but less exact, because in the case that $|E|<<|V|^2$, it is overkill.
Notice, however, that regardless of $|V|, |E|$, $O(|V|)$ is asymptotically better (at least as good as, and sometimes better than) $O(|V|+|E|)$.
I believe that this should clear things up, definitely if you make sure you really understand the answer.