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:
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 |
|
| 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, |
|
| Author: | efus [ Mon Oct 06, 2008 3:50 am ] |
| Post subject: | RE:Big theta notation |
Thank you, you have been a great help. |
|