In weeks 9 and 10 we learned about Big-Oh, Big-Omega, and Big-Theta.
Let's say we had the functions f(n) and g(n). The Big-3 essentially define the relationship between the growth of such functions as n approaches infinity.
In layman's terms:
1) f(n) is in Big-Oh of g(n) means that as n approaches infinity, the value of f(n) is always equal to or less than that of g(n)
2) f(n) is in Big-Omega of g(n) means that as n approaches infinity, the value of f(n) is always equal to or greater than that of g(n)
3) f(n) is in Big-Theta of g(n) means that as n approaches infinity, the value of f(n) is always equal to g(n), or greater than some constant*g(n) and less than some other constant*g(n)
There are many important practical applications of these definitions. For example, when you are interested in finding out how the polynomial running time of one algorithm compares to another, you can formalize such a comparison by defining their relationship in terms of statements 1 through 3. This creates a common basis for the communication of algorithm run-time comparisons between computer scientists and removes unnecessary ambiguity.
Wednesday 3 December 2014
Week 7 & 8
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.
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.
Subscribe to:
Posts (Atom)