Sign in to follow this  
discodowney

Big O Notation questions

Recommended Posts

So in big O notation when nested loops are used its considered O(N2) (that 2 is supposed to be in superscript, so N squared, but the button wont work for me).

But is it only N squared if the nested loop is going through the same array? So if i have 1 array size 10 and another of size 3. If i nest the second in the first is that still considered O(N2)?

Also when is an algorithm O(N logN)? I know when its just O(log N).

Cheers

Share this post


Link to post
Share on other sites
[quote name='discodowney' timestamp='1298402613' post='4777644']
But is it only N squared if the nested loop is going through the same array? So if i have 1 array size 10 and another of size 3. If i nest the second in the first is that still considered O(N2)?
[/quote]

If you have 2 lists of different sizes, you have 2 "variables". Then it's O(N*P) (if you name them N and P). But that is interesting only if you care about what things become when the 2 get big.
If one array is always of size 10 and you're interested in what things become when the other array gets big (dimension N), then it's O(N).

I think you should try to understand the principle rather than getting ready made formulas that will not make sense to you anyway. Sorry I have no particular good link for that, but I guess there are a lot of articles around.

Share this post


Link to post
Share on other sites
[quote name='discodowney' timestamp='1298402613' post='4777644']
So in big O notation when nested loops are used its considered O(N2) (that 2 is supposed to be in superscript, so N squared, but the button wont work for me).

But is it only N squared if the nested loop is going through the same array? So if i have 1 array size 10 and another of size 3. If i nest the second in the first is that still considered O(N2)?

Also when is an algorithm O(N logN)? I know when its just O(log N).

Cheers
[/quote]

Big O notation is a big topic. To summarize some things the complexity is measured function of variables that change or might change from one instance of a problem to another. By having two arrays of size 10 and another of size 3, and you loop over them you might have the complexity of O(1) - constant or O(lengthArray1 * lengthArray2) - if the processing in both loops is constant, i.e does not depend on variable quantities with respect to problem instance. If length1 and length2 are always 10 and 3 then you have O(1), else if they always change you have O(lengthArray1 * lengthArray2).

An algorithm is O(N*logN) when you do N operations that have O(logN) complexity.

Share this post


Link to post
Share on other sites
You can also get O(n*log(n)) when you divide a problem of size n into two problems of size n/2 plus some O(n) computation, like MergeSort. See [url="http://en.wikipedia.org/wiki/Master_theorem"]this Wikipedia page[/url] for an explanation of why.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this