java algorithm complexity determination

[wobuaini]

hey, can anyone help me with these comlexity problems? I tried with myself but still want some clarifications..cheer,here is the code:

(a) public void printPow2(int[] values)
{
for (int i = 1; i < values.length; i *= 2)
System.out.println(values[i]);
}


(b) public void maxDifference(int[] values)
{
int max = 0;
for (int i = 0; i < values.length; i++) {
for (int j = i+1; j < values.length; j++) {
int diff = Math.abs(values[j]-values[i]);
if (max < diff)
max = diff;
}
}
return max;
}


(c) public int fac(int n)
{
if (n == 0)
return 0;
else
return n*fac(n-1);
}


(d) public int silly(int n)
{
int tally = 0;
for (int i=0; i < n; i++) {
for (int j=n; j < n; j--) {
tally += 1;
}
}
return tally;
}

so the question is to find the running time comlexity of each question,with input size n,and it is for the worst case.
so my solution is (a)O(n),since the for loop tests n/2 times(or is it n/2 +1 times?need clarification), i*=2 excutes n times, so total of n/2+n=O(n).(does the system.out count by O(1)?)
(b)O(n^2) since only the nested loop dominant
(c)need help with this
(d)O(n^2) as for (b)

cheers in adevance,its kinda urgent please help..

[apines]

(a) i=i*2 means that the loop will iterate for log2(n) times, therefore your complexity for the first problem is O(log2(n)). All other operations such as System.out can be counted as O(1).
(b) Correct.
(c) Think how many times the recursion is called. It is like a loop iteration, all the other operations except the recursion call is O(1), the recursion is called n times, therefore the complexity will be O(n). You can write the same formula using a loop, and then you'll be able to see it more clearly.
(d) Correct.

[wobuaini]

Thanks a lot, apines.
still got a question.well, it is said to calculate the worst case,well i know it is just the longest time it could be,right? so it is just the normal way that we find the big-oh,like what i did,right?
another one, for the for loop for (int i = 1; i < n; i++),i know it doesn't affect the big-oh,but does this for loop test n times or n+1 times?
thx
:)

[apines]

if the init is i=1, then it runs n-1 times, because it does not run when i=n. In the examples below as far that I can see there is no difference between worst case and other cases.
Take an example of a sorting algorithm - you get an array of integers and you need to sort them from the smallest to the biggest. If our algorithm is bubble sort then the worst case scenario will be that the entire array is reversed - from biggest to the smallest - we will need to much more work that way, and our complexity will be O(n^2). The best case is that the array is already sorted, in which we will use O(n) complexity.