Big O notation troubles

[paintstripper88]

I have two functions, one of them recursive, the other calls the recursive function from within a loop. Here is the code.


void main5(int n)
{ for (int i=1; i<n; i*=2)
System.out.println(p(1, i));
}

int p(int i,
int n)
{ return 1+(i+1>n?0:p(i+i, n));
}


The output from calling main5(10) is:

1
2
3
4

I thought that the function p had a big o time complexity of O(n) but I think that might me wrong.

Assuming I am right, the time complexity of the function p should be magnified by the loop by 2n so the total time complexity should be 2n*n = 2n^2 = n^2.

Is that right, and am I right about the time complexity of p?

Thanks.
Paintstripper

[cilu]

I don't see any loop in p, except for the recursion. Well, I'm not very good with this, but as the way I see it, complexity for p is O(n) indeed.