Sign in to follow this  
_Sigma

[Big-Oh] Performance analysis help needed

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[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!!!

Share this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
Share on other sites
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!


Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this