Help In Learning Algorithm Basics

Question

Hi Guys,

I am learning algorithms and need you guys to help me. I am a beginner so forgive me if my question is not clear. Whiles am learning i am seeing something like NlogN, N^2 etc.. and something like that.

I don't really understand it clearly when it comes to checking the efficiency/performance of different algorithms using these notations. I understand Logarithms very well but the way they are been used in relation to checking algorithms performance makes me mad.

I am asking if someone can point me to a tutorial where such notations are been explained so that i can get the basics very well. I really want to understand them and am willing to learn.

Thanks for your help.

Kap.

Answer 1

Buy Introduction to Algorithms. You can get a second hand version at an affordable price.

And/or view these great online video lectures from MIT built around aforementioned book.

By viewing those lectures, you'll understand how some algorithms have logarithmic time complexity, whereas some have exponential, etc.

Answer 2

What you've described is called big O notation. Here is a guide explaining it.

An important thing to notice is that the notation ignores insignificant terms. If your algorithm takes 6X^2 + 3X + 12 seconds to execute, where X is the number of data points being processed, just call it O(X^2) because when X gets big, the 6 won't really make a difference, nor will the 3 nor the 12.

Answer 3

http://www.amazon.com/Structures-Algorithm-Analysis-Allen-Weiss/dp/0805390529 is one of the best books which will explain Algorithms in excellent way.

--Cheers

Answer 4

This is a pretty good explanation

Answer 5

Those are just functions, receiving the number of items in input, and returning how many operations it takes to complete the algorithm (usually they return the limiting factor of the algorithm, and not a specific function.. more on that - here).

Answer 6

You're talking about Big-O notation. This notation is a way of describing the worst possible running time of an algorithm as a function of its input size.

O(n^2) means that if the input has a size of n (such as a list with n elements in it), the algorithm will require n^2 passes through to execute in the worst-case scenarion (Big-O is worst case; there are other notations for best-case and average case). This could happen if you have a a for loop nested inside another, and both run from 1 to n.

O(nlogn) is similar. It usually happens when you are traversing a tree structure (such as a binary tree).

Note that you will probably never see something like O(3n) because for very large values of n, the constant 3 doesn't matter much, so it would be simplified to O(n).

Many of the others have already posted good links to read at.