1
$\begingroup$

Algorithm $X$ proceeds by recursively solving $5$ subproblems of one-half the size, then combining the solutions in $O(n\log n)$ time.

Algorithm $Y$ makes $9$ recursively calls on subproblems with one-third the size, then combining the solutions in $O(n^2)$ time.

What do the last parts of these sentences mean? "Combining the solutions in $O(...)$ time? Can we represent $X$ and $Y$ by:

$$X(n) = 5X(n/2)+n\log n$$

$$Y(n)=9Y(n/3)+n^2$$

Or does it mean something different?

$\endgroup$
2
  • 1
    $\begingroup$ I think you're right. $\endgroup$
    – Traklon
    Commented Oct 23, 2014 at 7:05
  • 2
    $\begingroup$ I think you may need to to put $O(\cdots )$ on the right hand side, or at least multiply $n \log n$ and $n^2$ by unknown constants $\endgroup$
    – Henry
    Commented Oct 23, 2014 at 7:15

0

Reset to default

You must log in to answer this question.