Complexity Classes and their Graphs: Behind the Scenes!
Welcome Hi! Welcome to this section on Complexity Classes and their Graphs . First of all, congratulations on these weeks of hard work!! : ) You’ve done a fantastic job and we’re so glad you’ve come this far. You learned in lecture that algorithms have different running times and how the orders of growth tell you how efficient an algorithm is, given very large inputs. The order of growth is an approximation, an upper bound on how much an algorithm could take to run, the worst-case scenario. We will first have a quick introduction to 2-D graphs and then we’ll discuss and illustrate the logic behind each complexity you’ve learned (constant, logarithmic, linear, loglinear, polynomial and exponential). The Graph The complexity classes are represented with a graph . Graphs have two axes: The X-axis , a horizontal line (represented below with an orange line). The Y-axis , a vertical line (represented below with a green line). Each point on the graph has two co