Question
Show (a) the exact number of operations and (b) the Big-O estimate of the following:
void func(unsigned long n) // n is a large, positive number
{
int x=1, y=x--, z=--y+x;
for(; z<n; ++x, ++y)
{
if(x>n)
z=n;
if(x>=y && (x || !z)) // Watch out for short
// circuit evaluation here.
y++;
}
}
Explanation / Answer
Here is how the program executes: x= 1 y = 1 // y is assigned value of x before x is decremented x = 0 // this is x-- y = 0 // y is decremented before it is added to x z = 0 // begin for loop z n) is false if( x >= y && ( x || !z)), the !z executes. Since z = 0, !z is 1 and ( x || !z) evaluates to 1 or true. x = y, so x >= y is true. True and true is true, so y++ statement executes and y is now 1. Back to for loop: 1 is added to x, x = 1. 1 is added to y, y = 2. z n) is false. if( x >= y false) so back to for loop to increment x and y. if conditions will evaluate to false until x is finally > n causing the if (x > n) to be true, then z = n, for loop increments x and y and then for loop test z = y) n times, && once, !z once x || !z once. 5 + 3(n + 1) + n + 1 + n + 1 + 1 + 1 = 9 + 3n + 3 + 2n = 12 + 5n Big O(n)