Posted by: atri | September 27, 2010

## Lect 12: Runtime Analysis of GS Algorithm-II

In today’s lecture, we finished the implementation of the GS algorithm and proved that it can be implemented in $O(n^2)$ time. We also briefly looked at (examples of) graphs. The slides have been uploaded.

Next lecture, we will define graphs more formally and look at some basic concepts. (The material will be from Sections 3.1 and 3.2 in the book.)

Regarding #2, you have to argue convincingly that the run time of your algorithm is $O(f(n))$. If that means you need to provide details on how certain steps of your algorithm are implemented, then you should do that. Basically if you claim some step of your algorithm runs in such and such time, there should be no reason to doubt your claim.