user2053912
user2053912

Reputation: 203

Asymptotic notations

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

Answers (1)

David Eisenstat
David Eisenstat

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

Related Questions