ITEC 2620 Quiz: Assignment 3 Solution
Document Summary
This assignment includes one question and one short programming project. Explain why breadth- rst search and depth- rst search both run in o(v + e) time for a graph. G = (v, e) and start vertex v v . Soln: for bfs, initializing and updating the array reached is bounded by o(v ). |e| vertices are enqueued and dequeued into the queue q and an enqueue/dequeue operation takes constant time o(1). Hence in total, bfs takes o(v + e) times. The argument for dfs (with a stack instead) is similar.
