_Sigma 792 Report post Posted May 24, 2007 I'm in a data structures summer class and we are to find the "..worst-case time bounds for the methods..." in the snipet below. I've made an attempt and would like to know if I am on the right track. public class NumberList { int[] number; int capacity; public NumberList(int size) { number = new int[size]; capacity = size; } public void printDuplicates() { for(int i =0; i<capacity;i++) for(int j=0;j<capacity;j++) if(j!= i && number[j] == number[i]) System.out.println(number[i]) } public void fill(int r) { for(int i =0;i<capacity;i++) number[i]=(i*2+7)%r; } public boolean findNumber(int searchNumber) { boolean found = false; for (int i =0;!found & (i<capacity);i++) { if(number[i] == searchNumber) found = true; } return found; } public void summarize(NumberList otherNumbers) { for(int i =0;i<othernumbers.capacity;i++) { int currentNumber = otherNumbers.number[i]; if(findNumber(currentNumber)) System.out.prinln(currenNumber); } printDuplicates(); } } This is what I've done: public class NumberList { int[] number; int capacity; public NumberList(int size) { 1 number = new int[size]; 1 capacity = size; } public void printDuplicates() { n+1 for(int i =0; i<capacity;i++) n+1 for(int j=0;j<capacity;j++) n if(j!= i && number[j] == number[i]) p = unknown System.out.println(number[i]) } public void fill(int r) { n+1 for(int i =0;i<capacity;i++) n number[i]=(i*2+7)%r; } public boolean findNumber(int searchNumber) { 1 boolean found = false; n+1 for (int i =0;!found & (i<capacity);i++) { n if(number[i] == searchNumber) 1 found = true; } 1 return found; } public void summarize(NumberList otherNumbers) { n+1 for(int i =0;i<othernumbers.capacity;i++) { 1 int currentNumber = otherNumbers.number[i]; n if(findNumber(currentNumber)) p System.out.prinln(currenNumber); } 1 printDuplicates(); } } And for each method this is O(g(n)) NumberList O(1) PrintDuplicates O(n^3) I am unsure if I add over the for(...) or multiply Fill O(n) findNumber O(n) summarize O(n) For this one, do I need to add the O(g(n)) for printDuplicates() to the total? Many thanks!!! 0 Share this post Link to post Share on other sites
Driv3MeFar 1080 Report post Posted May 24, 2007 Since this is homework I don't want to give you any answers, but you seem to be generally on the right track.For printDuplicates, you have something like this:for (0...n) for (0...n) //do work...So, basically, you are doing n many things n many times. Think about how you would represent that in terms of complexity.Also, I don't know if you already know this, but I assume not since you write n+1 for a lot of things:O(n+c) is equivalent to O(n). 0 Share this post Link to post Share on other sites
thebolt00 181 Report post Posted May 24, 2007 One little thing to think about. In printDuplicates, how many time is the "if" done per iteration in the innermost loop? And what contribution does this give to the complexity of the overal function?Also, yes, in the case of summarize you should include any function it calls.Hope this wasn't more help than what the forum gods thinks is appropriate...-M 0 Share this post Link to post Share on other sites
Antheus 2409 Report post Posted May 24, 2007 PrintDuplicates is wrong. The others look correct, at least given your simple "worst-case" requirement.The O notation can be used to estimate various performance criteria - your results give the worst-case, not average or minimal, although those are the same in some cases.It might also be worth mentioning that it depends on what you're measuring. If you're interested into just algorithm behaviour, then they are correct. If you're looking at how often System.out.println is called (by far the most expensive operation), then for some methods the value is different as well (although not necessarily worst case behaviour).Some of the methods also depend heavily on characteristics of input data, so the O() notation could reflect that as well. 0 Share this post Link to post Share on other sites
_Sigma 792 Report post Posted May 24, 2007 Quote:Original post by Driv3MeFarSo, basically, you are doing n many things n many times. Think about how you would represent that in terms of complexity.Alright. Is this right?the outer for(...) is nthe inner for is n*nand the if is going to be at worst less than n*n.so n+n*n+p = O(n^2)is this logic correct?Quote:Also, I don't know if you already know this, but I assume not since you write n+1 for a lot of things:O(n+c) is equivalent to O(n).Actually I do. Our prof wanted to make it clear that for(0..n) actually runs n+1 times, so if we are finding the full complexity we have to make sure the +1 term is there, so I just did it so I don't forget about it! 0 Share this post Link to post Share on other sites
Driv3MeFar 1080 Report post Posted May 24, 2007 Quote:Original post by _SigmaAlright. Is this right?the outer for(...) is nthe inner for is n*nand the if is going to be at worst less than n*n.so n+n*n+p = O(n^2)is this logic correct?Yep, that works. 0 Share this post Link to post Share on other sites
_Sigma 792 Report post Posted May 24, 2007 Cool. So summarize is now O(n^2) as well? 0 Share this post Link to post Share on other sites
Driv3MeFar 1080 Report post Posted May 24, 2007 Summarize is O(n + O(printDuplicates)), so yes. 0 Share this post Link to post Share on other sites