# Big O Notation questions

This topic is 2697 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## 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 on other sites

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)?

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 on other sites

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

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 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 this Wikipedia page for an explanation of why.

1. 1
2. 2
Rutin
21
3. 3
JoeJ
17
4. 4
5. 5

• 37
• 23
• 13
• 13
• 17
• ### Forum Statistics

• Total Topics
631705
• Total Posts
3001823
×