Big theta notation

[efus]

Hi,

I need to make a big-theta notation on an algoritm I made. The algoritm is soposed to find factors of a number. This is the algoritm implemented in java:

public class factor {

public static void main (String argv[]) 
{	
	int number =(Integer.parseInt(argv[0]));
	int counter = 0;

	for(counter = 1 ; counter <= number/2 ; counter++)
	{
		if(number % counter == 0)System.out.println(counter);
	}
	System.out.println(number);
}
}

I figured the theta notation to this is: O(N)

 

The problem is now that i need to express big theta as a function of of the length of N (the number

of bits in N). I have no idea what I am supposed to do here? I would greatly appreciate if anyone could help.[/code]

[Aeternus]

Well consider that given a number n, you need [math]\log_2(n)[/math] bits to display it, so you have

 

[math]

N = \log_2(n) [/math]

[math]2^N = 2^{\log_2(n)} [/math]

[math] 2^N = n

[/math]

 

So you are left with [math]O(2^n)[/math].

 

Two points to note :

 

a) Big O and Big Theta are two different things. Big O is only an upper bound, whereas Big Theta is much tighter and must be also a lower bound. See http://en.wikipedia.org/wiki/Big_O_notation#The_family_of_Bachmann-Landau_notations .

 

b) You only need to check for factors up to [math]\sqrt{n}[/math] rather than [math]\frac{n}{2}[/math]. Consider a number bigger than the square root, then you'd need to multiply it by a number smaller than the square root to get n, otherwise you'd get a number larger than n.

[efus]

Thank you! I get it now. You have been a great help