Guys iam trying to learn algor...




Comment hidden because of low score. Click to expand.
1
of 1 vote

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.

Ex: 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.

- Anonymous November 01, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Thanks dude but tell me when the term 'log' comes into picture...like O(logN) or O(NlogN)..what does this log indicate in terms of time complexity.

- sastry.soft November 07, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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)

- Selmeczy, Péter November 01, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- sastry.soft November 01, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

If you try to understand algorithms and their complexity without mathematical background - it is a kind of mission impossible. Good luck with it - you gonna need it!

- Selmeczy, Péter November 02, 2012 | Flag




Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More