During weeks 7 and 8 we learned about sorting algorithm complexity.
The particular kind of complexity we are interested in is time complexity. More specifically, time in terms of the number of steps required to execute an algorithm given a certain input, and NOT the amount of time in seconds, minutes, hours, etcetera. This definition of time complexity allows computer scientists to think of the running time of an algorithm independent of the hardware on which it is being run.
In order to count the steps, we have to differentiate between which portions of the code will run an input-dependent amount of times versus a static number of times. For example, the contents inside of a for-loop which iterates over a list of size n will each be executed n times-- once for each element. A variable initialization statement outside of the for-loop on the other hand will be executed a single time, hence being input-independent. The sum of these two distinct types of code will determine the overall running time in terms of steps of a given algorithm.
No comments:
Post a Comment