# [Big-Oh] Performance analysis help needed

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

## Recommended Posts

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)
System.out.println(number)

}

public void fill(int r)
{
for(int i =0;i<capacity;i++)
number=(i*2+7)%r;
}

public boolean findNumber(int searchNumber)
{
boolean found = false;
for (int i =0;!found & (i<capacity);i++)
{
if(number == searchNumber)
found = true;
}

return found;
}

public void summarize(NumberList otherNumbers)
{
for(int i =0;i<othernumbers.capacity;i++)
{
int currentNumber = otherNumbers.number;
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)
p = unknown							System.out.println(number)

}

public void fill(int r)
{
n+1				for(int i =0;i<capacity;i++)
n					number=(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 == 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;
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!!!

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

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

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

##### Share on other sites
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 n
the inner for is n*n
and 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!

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

##### Share on other sites
Cool. So summarize is now O(n^2) as well?

##### Share on other sites
Summarize is O(n + O(printDuplicates)), so yes.