I have program like this on labs
int fun( int n )
{
if (n==0) return 0;
else return fun(n-1) +1;
}
And professor say that function is O(2^n). I Can't understand why, every time I count O I get O(n)
Anybody can explain it to me ?
-
2it is O(n)...your prof is wrong LOL...which university btw?Steve– Steve2014-11-08 22:12:30 +00:00Commented Nov 8, 2014 at 22:12
-
now, there is a simple way to verify who is right, for simple questions like this you can just sub in some numbers and count the # of operations, O(2^n) means it will always be greater than c*2^n. in this example c cannot be < 1 so if you sub in 10 you can see it is clearly not the caseSteve– Steve2014-11-08 22:19:26 +00:00Commented Nov 8, 2014 at 22:19
-
Well "like this" may be dangerous. What problem do you solve with that recursion method? (of course, in this method, you are right, it is O(n)).libik– libik2014-11-08 22:21:17 +00:00Commented Nov 8, 2014 at 22:21
-
@libik by like this i mean something can be easily countedSteve– Steve2014-11-08 22:22:17 +00:00Commented Nov 8, 2014 at 22:22
-
I doubt your professor thinks this code solves the tower of hanoi. It clearly does not. It solves the problem "needlessly count from n to zero".usr– usr2014-11-08 22:23:15 +00:00Commented Nov 8, 2014 at 22:23
|
Show 1 more comment
1 Answer
int fun( int n )
{
if (n==0) return 0; //1 operation for the base case
else return fun(n-1) +1; //n-1 operation in total
}
we can look at it backward, lets say you are at the base case now, you will do one return 0; which is O(1), and then one level up you will return 0+1; which is also O(1). How many times are you going to return? well the answer is simple, n times, so n*1 = n => O(n). if you want to be exact, you are doing one comparison, one addition and one return each time you recurce, so that makes it 3*n - 1 in total which is still O(n)
