ganesh swamypillai

Greenhorn
+ Follow
since Oct 13, 2014
Merit badge: grant badges
For More
Cows and Likes
Cows
Total received
0
In last 30 days
0
Total given
0
Likes
Total received
1
Received in last 30 days
0
Total given
0
Given in last 30 days
0
Forums and Threads
Scavenger Hunt
expand Ranch Hand Scavenger Hunt
expand Greenhorn Scavenger Hunt

Recent posts by ganesh swamypillai

I was saying that for the example code:

for(i=0;i<n;i++)
{
j += i;
}

For the above code, Time complexity of code is O(n) = Omega(n) = Theta(n).
In other words, the running time will be of the order of n.

Definitely, O(n^2) != O(log(n)), as running time taken as logarithmic is not same as running time being taken as quadratic.
9 years ago
For this particular example, Big O = Omega O = Theta O = 2n
9 years ago
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









9 years ago
Please check in this link: Importance of Override annotation.

Also check StackOverflow

Basically, consider creating a set of employee objects and equals() method is not having override annotation, then set will contain duplicate entries.

Compiler will not invoke employee's equals() method, but equals() of Object.

Suppose, you intended to override a method, but suppose your method's signature is wrong compared to superclass, then compiler will flag, if @Override annotation is used.



9 years ago