discodowney 102 Report post Posted February 22, 2011 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 0 Share this post Link to post Share on other sites
SriLumpa 198 Report post Posted February 22, 2011 [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. 0 Share this post Link to post Share on other sites
Deliverance 387 Report post Posted February 26, 2011 [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. 0 Share this post Link to post Share on other sites
alvaro 21272 Report post Posted February 26, 2011 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. 0 Share this post Link to post Share on other sites