Computer Science Canada

Big theta notation

Author:  efus [ Sat Oct 04, 2008 4:09 pm ]
Post subject:  Big theta notation

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:
code:

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]

Author:  Brightguy [ Sat Oct 04, 2008 5:27 pm ]
Post subject:  Re: Big theta notation

You want to rewrite N in terms of its length, which is O(log N).

BTW, though it doesn't matter asymptotically, you can easily tighten the loop to get a algorithm.

Author:  efus [ Sat Oct 04, 2008 5:58 pm ]
Post subject:  Re: Big theta notation

what do you mean by "rewrite N in terms of its length"? this is the part I dont get

Author:  Brightguy [ Sat Oct 04, 2008 7:03 pm ]
Post subject:  Re: Big theta notation

Let n be the number of bits in N, . Determine the running time of your algorithm in terms of n. After all, this is what you'd be interested in if you were going to run the algorithm.

Author:  efus [ Mon Oct 06, 2008 3:50 am ]
Post subject:  RE:Big theta notation

Thank you, you have been a great help.


: