Asymptotic notation is a very important concept in computer science, which again uses maths to introduce itself to the world,in fact it's a pure mathematical notation used to analyse the complexity of algorithms(how much space and time an algorithm takes to execute in a certain machine) and whose goal is simply avoiding the constants in studying and analysing algorithms.ok,but what these contants are ? you know every machine has its own capabilities or characteristics, particularly how much processor's speed has it ? how much memory has it? and more,but just focus on these two,they differ from one computer to another,here comes the problem because if we wanna study the behavior of an algorithm ,we can not test it on every machine in the world,either we can not test it in one machine and say here is its speed and the amount of memory it takes ,because machines are differents, it will be certainly fast in a machine with more speed ,and even with machines with the same speed and memory,no one knows the state of the machine when testing the algorithm ,i mean by the state how many programs the user executes in the time of the test and other conditions .which, in no doubts, affect our test ,so the constants which affect the good and perfect study of algorithms are these machine's speed and memory ammount.
The asymptotic study of algorithms doesn't answear exactly,with how much speed the algorithm runs,but instead it describes the behavior of the algorithm when the data processed by the algorithm becomes bigger and bigger,so it give us the order of the algorithm's speed
for example if we say that the algorithm A runs in the order of n² that's O(n²)using the Big-O notation(n is the amount of processed data) we give the user a garantie that the algorithm runs
in a time which's the cube of the processed data and never exced this time whatever is the machine used to run the algorithm.
please watch the lecture to understand more
Asymptotic Notation, Recurrences, Substitution, Master Method
No comments:
Post a Comment