[Big-Oh] Performance analysis help needed

Started by
6 comments, last by Driv3MeFar 16 years, 10 months ago
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!!!
Advertisement
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).
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
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.
Quote:Original post by Driv3MeFar
So, 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!


Quote:Original post by _Sigma
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?



Yep, that works.
Cool. So summarize is now O(n^2) as well?
Summarize is O(n + O(printDuplicates)), so yes.

This topic is closed to new replies.

Advertisement