Reputation: 203
From what I have studied: I have been asked to determine the complexity of a function with respect to another function. i.e. Given f(n)
and g(n)
, determine O(f(n()
. In such cases, I substitute values, compare both of them and arrive at a complexity - using O(), Theta and Omega notations
.
However, in the substitution method for solving recurrences
, every standard document has the following lines:
• [Assume that T(1) = Θ(1).]
• Guess O(n3) . (Prove O and Ω separately.)
• Assume that T(k) ≤ ck3 for k < n .
• Prove T(n) ≤ cn3 by induction.
How am I supposed to find O and Ω when nothing else (apart from f(n)) is given? I might be wrong (I, definitely am), and any information on the above is welcome.
Some of the assumptions above are with reference to this problem: T(n) = 4T(n/2) + n
, while the basic outline of the steps is for all such problems.
Upvotes: 0
Views: 383
Reputation: 65447
That particular recurrence is solvable via the Master Theorem, but you can get some feedback from the substitution method. Let's try your initial guess of cn^3
.
T(n) = 4T(n/2) + n
<= 4c(n/2)^3 + n
= cn^3/2 + n
Assuming that we choose c
so that n <= cn^3/2
for all relevant n
,
T(n) <= cn^3/2 + n
<= cn^3/2 + cn^3/2
= cn^3,
so T
is O(n^3)
. The interesting part of this derivation is where we used a cubic term to wipe out a linear one. Overkill like that is often a sign that we could guess lower. Let's try cn
.
T(n) = 4T(n/2) + n
<= 4cn/2 + n
= 2cn + n
This won't work. The gap between the right-hand side and the bound we want is is cn + n
, which is big Theta of the bound we want. That usually means we need to guess higher. Let's try cn^2
.
T(n) = 4T(n/2) + n
<= 4c(n/2)^2 + n
= cn^2 + n
At first that looks like a failure as well. Unlike our guess of n
, though, the deficit is little o of the bound itself. We might be able to close it by considering a bound of the form cn^2 - h(n)
, where h
is o(n^2)
. Why subtraction? If we used h
as the candidate bound, we'd run a deficit; by subtracting h
, we run a surplus. Common choices for h
are lower-order polynomials or log n
. Let's try cn^2 - n
.
T(n) = 4T(n/2) + n
<= 4(c(n/2)^2 - n/2) + n
= cn^2 - 2n + n
= cn^2 - n
That happens to be the exact solution to the recurrence, which was rather lucky on my part. If we had guessed cn^2 - 2n
instead, we would have had a little credit left over.
T(n) = 4T(n/2) + n
<= 4(c(n/2)^2 - 2n/2) + n
= cn^2 - 4n + n
= cn^2 - 3n,
which is slightly smaller than cn^2 - 2n
.
Upvotes: 2