Have coffee, Read below statements.
In the beginning, you have a problem.
There is a
problem you are trying to solve.
Objective1:Now your objective is solve that problem.
That program performs few logical steps to solve the problem.
Set of logical steps forms '
algorithm'.
Any problem contains data to be worked on to solve it.
Call it '
input'.
data will have size.
Call it '
input size'
You have written a program to solve that problem.
Objective1: achieved. You are happy.
Now, curiousity is awakened to go to next objective.
Objective2: I want to know how much time is taken to run my program for that problem.
Basic Solution: You can put timestamp at start of program and end of program and with difference.
Objective2: achieved. You are happy.
Now, curiousity is awakened to go to next objective.
Program acts on data provided. What if I keep changing size of data and same program is run?
Will it take same time?
Objective3: I want to know how much time is taken to run my program for that problem, by varying size of data fed to the program.
Basic Solution: You can put timestamp at start of program and end of program and with difference, keep increasing the size of data fed to the program.
Objective3: achieved. You are happy.
Now, curiousity is awakened to go to next objective.
What if you are curious to find out for large size of input, how your program behaves, without running your program?
Objective4: I want to know how much time is taken to run my program for that problem, for large size of the program,
without running your program.
Asymptotic means exactly that: for large size of input, what happens?
You want to analyze your program( concrete representation of algorithm) and find out how it behaves.
Basically your objective is to do asymptotical analysis of your algorithm.
If you are not running your program, how will you know how much time it will take for large input?
By studying your code,
by finding out how many loops are present in your code?
by finding out how much extra space you need to solve your problem?
by finding out how many operations you perform in each of the loops, how much extra space your code creates/uses?
How do you study your code? try analyzing by varying n , give it some value, and list out no. of operations it does to finish that loop.
Take an example code: Suppose your program is as follows:
Let n be input size.
for( i = 0; i< n; i++)
{
j+=i;
}
print j;
If you see above code, what are the operations you can do? addition, assignment, looping, incrementing. ( incrementing is addition)
Restrict operation to addition.
Suppose n = 20;
How many additions are happening?
For i, 20 additions,
For j, 20 additions,
So totally 40 additions.
Or 40 operations is being performed by above code.
If n = 60, then how many operations? It will be 120.
Now keep increasing n. Basically, you know that you can arrive at a mathematical formula and say, the program will perform 2n operations.
Assume that your machine says that for each operation, it is taking 1 second, then you can say that your program will take 2n seconds for input size equal to n.
You can also make a statement that your program will take atmost 2n seconds or it will perform
atmost 2n operations.
When you say, 'atmost' 2n operations, thats where you get your Big O ( jargon ).
OR
When you say, 'atmost', you say that it is the upper bound.
When you say, 'atleast', you say that it is the lower bound.
OR
You are trying to say, that your program will do atleast 2n operations to solve the problem.
When you say, 'atleast' or 'lower bound', thats where you get your Omega ( jargon ).
If you say that your program will perform exact 2n operations, then thats where you are dealing with Theta ( jargon ).
When you can say, 'exact', it is a tight bound. which is theta.
Basically, theta, omega, Big O, are all theoritical notations to say that
your algorithm will do exact number of operations, atleast those many operations, atmost those many operations respectively.
OR
theta --> exact number of operations --> tight bound
omega --> atleast those many operations --> lower bound
Big O --> atmost those many operations --> upper bound
Objective4: achieved. You are happy. Without running your progrem, you came to know if you keep increasing input, how much time will program take.
Now, curiousity is awakened to go to next objective.
I have many problems which I have solved. I have written programs to solve those problems.
People had many problems to solve. People wrote many programs to solve those problems.
Now, for same problem, two people wrote their own idea, their own algorithm, their own program, their own set of operations to solve the problem.
Now, I want to know for same set of input given to both the guys, how much time will their program take as size of input keeps on increasing.
Objective5: You want to compare behavior of two different algorithms on same problem as size of input increases.
You want to compare behavior, meaning you want to see how many operations each algorithm does to solve the same problem.
Or by knowing how many operations each algo does, you can tell how much time it will take. Or in other words: runtime complexity. ( jargon )
Obviously, anyone will want to run the algo whose runtime complexity is less.
Solution: Make someone analyze how many operations are performed by two algorithms and compare the behaviour.
Objective5: achieved. you are happy. You can compare runtime complexity of algorithms and select which one is efficient.
Now, curiousity is awakened to go to next objective.
I have written program to solve a problem. My friend also wrote a program to solve same problem.
We both compared our program's behaviour. We found that my program does more operations than his program.
Objective6: Optimize. Once you find runtime complexity of a algorithm, try to minimize complexity. If it is O(n^2), try making it O(n). If it is O(n), try making it O(1) etc.
At each objective level, different people have taken different objectives and theory of algorithms have grown.
Hope it was helpful. Please correct me, if I have gone wrong somewhere.
This can be a starting point for you to dive deep, if I am not wrong.
Hope your coffee is still there. You can sip some more.
All the best