Help with Big Oh and # of operations
I'm having trouble with caluclating the number of operations and big Oh notation for the below code. Help would be greatly appreciated.
staticint bar(int a,int n)
{
int k = n;//1 operation
int ans = 1;//1 operation
int temp = a;//1 operation
do
{
if (k % 2 == 0)//if k is an even number// operations
{
k = k/2;//reduces k by a factor of 2// operations
temp = temp * temp;// operations
}
else//if k is an odd number, turns it to a even number
{
k = k -1;// operations
ans = ans * temp;// operations
}
}
while (k > 0);//n-1 operations
System.out.println(ans);
return ans;//1 operation
//total operations
//big Oh =
//output using (3,6) = 729
}//end bar
}//end class
[1971 byte] By [
Stumpeda] at [2007-10-2 0:16:00]
The intitiation of some variables are not concidered to be operations. The number of operations is the number of times your code runs the do-while loop. Every time the loop execute's it adds O(1) to your operation total. The number of operations are only dependend on the value of k, which is either divided in half, or 1 is subtracted. So with every loop the value of k always gets less.
This should be enough for you to finish the assignment. Here's also a link to a fairly simple tutorial on "Complexity and Big-O Notation":
http://www.cs.wisc.edu/~hasti/cs367-common/notes/COMPLEXITY.html
Good luck.
Something else that it is useful to note is this:
Any time k is even you cut it in half, any time it is odd you convert it to even so the very next time through the loop it will be cut in half.
So in the best case (a perfect power of 2) you would cut it in half every single time, a pattern of even, even, even, even....
But in the worst case it is odd, even, odd, even, odd, even, odd, even...
This is still cutting it in 2 every other time which is at worst only twice as long as the first case.
In the same way that you ignore constant set up times, meaning that you don't distinguish between something that is O(N) and something that is O(N + 3) you don't distinugish between something that is just a constand factor longer. So something that is O(N) and O(2N) or even O(1/2*N) are all considered to be the same O(N).
I'm not saying your code is O(N). It's not. What I'm saying is that in this particular code, the classic fast integer power routine, your loop is dominated by the factor of 2 reduction which happens at least every other time through the loop. Or looked at differently, you could have just as easily written the code so that the loop ALWAYS divides k by two, it would first test if it was odd and reduce it to even and then immediately do the even step.
