0
$\begingroup$

In divide-and-conquer, one uses the following formula to find the runtime:

$$T(n) = aT(n/b) + f(n).$$

I am confused with the meaning of the constants $a$ and $b$, as well as by the question of how to find $f(n)$. The textbooks could not help me. In exercises, one usually gives this data and asks about the runtime. The master theorem then provides the cases based on these values.

Let's take the following example. Given a square of length $n = 2^k, k \in \mathbb{N}$, I need to divide it into 4 equal squares by a horizontal and vertical line crossing each other in the center. I will proceed like this in each smaller square until I get a square of length 2. How do I get $a$, $b$, $f(n)$, and eventually the runtime?

$\endgroup$
1
  • $\begingroup$ You don't provide enough information to solve completely. $\endgroup$
    – user16034
    Sep 18, 2022 at 17:57

2 Answers 2

1
$\begingroup$

Your example is a bit weird, because you are not describing a problem you are trying to solve for a given length $n$… For the explaination, suppose you want to count the number of ships (like in battleship game) present in the square. Suppose, for simplicity purposes, that no two battleships touch each other.

  • $a$ is the number of subproblems, aka the number of times you have to make a recursive call. Here, since there are $4$ smaller squares, that would mean $a = 4$ ;
  • $b$ is the factor by which the size is divided. Since you consider the length of the square, the $4$ smaller squares are of length $\frac{n}2$. That means that $b = 2$ ;
  • $f(n)$ is the additionnal time needed to reconstruct a solution of size $n$ given all solutions of size $\frac{n}b$. Here, you have to add all solutions, but there could be some duplicates, for example if a ship has parts of it in two adjacent squares. To substract those, you would need to go over all four borders and verify if there is a ship across the border. You would need $\mathcal{O}(n)$ time to make this verification.

Overall, the complexity would verify : $T(n) = 4T\left(\frac{n}2\right) + \mathcal{O}(n)$.

To solve it, you can use the master theorem. You get $T(n) = \mathcal{O}(n^2)$.

$\endgroup$
8
  • $\begingroup$ @YvesDaoust The borders contains $2n$ $1\times 1$ blocks. You'd need $\mathcal{O}(1)$ time for each block to check if there is a ship crossing the border. $\endgroup$
    – Nathaniel
    Sep 18, 2022 at 18:04
  • $\begingroup$ @YvesDaoust I am not quite sure what your comment means. Perhaps the simplication I made clears out your doubts? $\endgroup$
    – Nathaniel
    Sep 18, 2022 at 18:10
  • $\begingroup$ Sorry, I missed your boats. Bad day today... $\endgroup$
    – user16034
    Sep 18, 2022 at 18:13
  • $\begingroup$ Thanks. How do you get from there $O(n^2)$ following the master theorem given that $\log_2 4 = 2$ ? $\endgroup$
    – user153448
    Sep 18, 2022 at 19:18
  • $\begingroup$ @user153448 Here, $f(n) = \mathcal{O}(n) = \mathcal{O}(n^c)$ with $c = 1$. Since $c< log_b a$, the solution is $\mathcal{O}(n^{\log_b a}) = \mathcal{O}(n^2)$. $\endgroup$
    – Nathaniel
    Sep 18, 2022 at 19:45
0
$\begingroup$

Hints:

You can guess this information from the equation itself.

In $T(n)$, $n$ denotes the size of the problems. So in $T\left(\dfrac nb\right)$, $\dfrac nb$ must be the size of the subproblems.

Now the $a$ in $aT\left(\dfrac nb\right)$ must be the number of subproblems that are effectively solved.

Finally, $f(n)$ is an extra cost attributed to the divide and the conquer operations.

$\endgroup$
2
  • $\begingroup$ $T\left(\frac{n}b\right)$ is not the size of the subproblems, it is the cost to solve one subproblem. Also, there are not $b$ subproblems. Finally, why would $a$ be smaller than $b$? $\endgroup$
    – Nathaniel
    Sep 18, 2022 at 18:02
  • $\begingroup$ @Nathaniel: you are right, I fixed those inaccuracies. Thanks. $\endgroup$
    – user16034
    Sep 18, 2022 at 18:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.