questions from time complexity

[ckbest]

any idea about the time complexity of following code?
1)
-------------------------------
i=1;
while(i <=n )
{
x = 2 * x;
i = i +2;
}

1) O(X^2)
2) O(X^n)
3) O(X^2/n)

-------------------------------

2) Let “rest(i)” return a sub array that is an part of array from i+1th elements to the end of original array. Then how many times will the following function be called in worst case?

Int Function( int[] a, int[] b){

Int i=0, j=0;
If( a[i] == b[j])
Return Function( rest(i) , rest(j)) +1;
Else
Return max(function(rest(i), rest(j+1)), function(rest(i+1),rest(j));
}

A. O(N) B. 0(nlogn) C. … D… E. O(2^n)

[bahri]

q1 loop executes n/2 times so O(n/2) equals O(n) but i dont understant x,

is it a variable ? if so it must not have an effect to complexity

[bahri]

for q2) think T(0) as 1, and if n is the sum of the length of array a and array b,

and T(n) is running time of function([a],[b]) then there are two cases.

--------------------------------------------------------------

on the first Return Function( rest(i) , rest(j))

T(n) = T(n-2) + very small time (vst)

T(n) = (T(n-4) + vst) + very small time

T(n) = ((T(n-6) + vst) + vst ) + very small time

.
.
.
.

T(0) = (T(n - n) + vst .........


so T(n) = [(n/2) * vst] equals O(n/2) equals O(n)

--------------------------------------------------------------

on the second return function

Return max(function(rest(i), rest(j+1)), function(rest(i+1),rest(j));

T(n) = 2 T(n-1)

so

T(n) = 2 (2 T(n-2))
T(n) = 2(2(T(n-3)))
.
.
.
.
T(n-n) = (2^n) T(0) = O(2^n)

----------------------------------------------

if function 2 return always the worst runtime is exponential one 2^n