I have an algorithm that does O(n) work, gets rid of a constant fraction 1/k of the input (k > 2), and calls itself recursively on what remains. The algorithm can be described by T(n) = T( ( (k-1)/k)*n)+O(n). How do I calculate the closed form for T(n).
Add a comment
|
2 Answers
You can expand it directly: T(n) = T(((k - 1)/k)^2 * n) + O(((k - 1)/k) * n) + O(n) and so on
Note that n * ((k-1)/k) is n / (k / (k - 1)) which implies a denominator > 1.
Hence it is a geometric series that converges to a sum n / ( 1 - (k - 1)/k) = n * k.
Hence T(n) = O(n*k) which is O(n) if k is constant.
6 Comments
griffin
isn't O(n*k) the same as O(n) in terms of algorithmic complexity? (really only know basics about this stuff, but i'd be interested)
user1952500
If the input has something to do with k then it isn't. For example there may be k colors and n boxes and a coloring algorithm's complexity may depend on both.
user1952500
If the denominator is > 1 the sum has an upper bound. Else it will be unbounded, I.e. infinite.
griffin
Ah okay, so for every constant k which is defined ahead and may not change depending on input, O(n) and O(k*n) would be the same, but for every k which depends on the input or could change, it won't be the same? But then k isn't a constant anymore or? Confused.
user1952500
Yes, you're right. The problem mentions k as a constant. Edited.
|
You might want to read about the Master Theorem, which is a convenient way to analyze this kind of problems: http://en.wikipedia.org/wiki/Master_theorem
Your algorithm would fall into case 3, where the recursive work is negligible compared to the work outside.
