Guys iam trying to learn algor...
No-one will write you an intro like this here - lack of space :)
Get/buy and read this: Introduction to Algorithms [Student Edition] [Paperback] by T Cormen (Author), C Leiserson (Author), R Rivest (Author), C Stein (Author)
if he still talk about functions f(n) and g(n) that will go for a toss...i need some clear english demonstration..i tried reading mark weiss but could not understand anything
The Big O notation is the upper bound on the time/space required by an algorithm. It indicates the worst case. Similarly,omega notation is the lower bound i.e. it indicates the order of minimum time/space required fro the algorithm.
- Anonymous November 01, 2012Ex: When I say my algorithm to traverse a list is O(n) (in time complexity), I mean the time required for my algorithm to run is bounded by (constant*n) from up. Remember, while denoting complexities of algorithms, the precise values of time required in best/worst cases are not important, only the order of the time required in terms of the input variable (n) matters.
As a beginner, just keep in mind that, in order to determine the time complexity of a given algorithm, we see how many times, we need to iterate over the input (or some function of the input) to get the task done. Again, the precise value is not important, just the number of iterations expressed as a function of the input variable is enough to indicate the Big-O value.
Example:
To display all the elements of a list, I iterate over all the elements in the list once i.e.we need one for-loop that runs over all the elements of the list. Thus, time required to execute my display algorithm can be expressed in terms of n (i.e. length of the list in this case) as opposed to logn, n^2 etc.
Thus, this algorithm has a time complexity of O(n).
Consider another example of adding two nXn matrices.
I need to iterate over all the elements of both the matrices and add the elements at the same position in the two matrices. Thus, I need to iterate over nXn times i.e. two for-loops, one over the rows and another over the columns for each row.
Thus, the time complexity of this algorithm is O(n^2).
HTH.