T (1) = c
T (n) = T (n/2) + dn
How would I determine BigO of this quickly?
+2
A:
Use repeated backsubstitution and find the pattern. An example here.
Matias Valdenegro
2010-10-31 00:08:32
+2
A:
I'm not entirely sure what dn is, but assuming you mean a constant multiplied by n:
According to Wolfram Alpha, the recurrence equation solution for:
f(n) = f(n / 2) + cn
is:
f(n) = 2c(n - 1) + c1
which would make this O(n).
Ani
2010-10-31 00:13:02
Oh wow wolfram does this too..thats crazy..but Id need to be able to do this kind of stuff on a test
fprime
2010-10-31 00:17:17
Could you clarify what you mean by "be able to do this kind of stuff on a test"?
Ani
2010-10-31 00:26:10
I want to be able to determine bigO of this function
fprime
2010-10-31 00:30:26
The BigO appears to be `O(n)`. Am I missing something?
Ani
2010-10-31 00:31:11
@Ani: He wants to know the *technique*, not the *answer*. (Isn't that obvious?)
j_random_hacker
2010-10-31 07:00:07
@fprime, @j_random_hacker: On re-reading, yes it does seem obvious now. Sorry, I missed that. Cheers.
Ani
2010-10-31 07:24:11
+1
A:
Well, the recurrence part of the relationship is the T(n/2) part, which is in effect halving the value of n each time.
Thus you will need approx. (log2 n) steps to get to the termination condition, hence the overall cost of the algorithm is O(log2 n). You can ignore the dn part as is it a constant-time operation for each step.
Note that as stated, the problem won't necessarily terminate since halving an arbitrary value of n repeatedly is unlikely to exactly hit 1. I suspect that the T(n/2) part should actually read T(floor (n / 2)) or something like that in order to ensure that this terminates.
mikera
2010-10-31 00:18:55
Hm I think you got into the same trap as I did. I'm so used to see BigO in the context of a computational complexity, that it was my first thought as well. But it's quite possible that the problem is in fact to determine the BigO for the solution of that recurrence :)
Maciej Hehl
2010-10-31 00:25:57
Having said that, I'm pretty sure you can compute the solution in O(1) if you are allowed to solve the recurrence.
mikera
2010-10-31 00:32:43
Yes :), but I suspect the question might be about the limiting behaviour of the solution, not of a computational complexity of computing T(n) given the solution. I might be wrong of course. Some say that the first impulse is the best :)
Maciej Hehl
2010-10-31 00:39:44