4
$\begingroup$

It seems to my uneducated mind that if I have $\frac{n}{k}$ subproblems, each of size $\Omega (k \log k)$, that my overall problem must be at least of size $\Omega (n \log k)$, by the reasoning that if I have $\frac{n}{k}$ things, each of which is at least $k \log k$, I should be able to multiply those together to get a lower bound for their sum.

However, my TA seems to disagree with me, stating that addition is not defined on $\Omega (f(x)) + \Omega (g(x))$, and therefore I can't sum or multiply the subproblems in this fashion.

I was wondering if someone could explain the error in my reasoning.

$\endgroup$
7
  • $\begingroup$ When you add two functions with the same lower bound you can get zero, or something much smaller than the original two functions if there is a cancellation. In terms of algorithms, it maybe possible to solve a big problem easier than the sum of its smaller versions, although I am not sure this is what you had in mind. I think you should clarify your question. Is it lower bound for the complexity of a problem, or of a specific algorithm, or is it a lower bound for memory? $\endgroup$
    – timur
    Jan 1, 2011 at 20:00
  • $\begingroup$ @Timur, it's a complexity problem. The particular problem we were assigned had to do with the lower bound on the number of comparisons necessary to sort a set if I knew that it was already pre-sorted in some way. $\endgroup$
    – dsolimano
    Jan 1, 2011 at 21:15
  • 1
    $\begingroup$ I can say that in general you cannot just add complexities, you need some additional reasoning to justify what you are doing. I suggest you to think carefully, and it may help not to use undefined words such as "sum of problems" because they give a false impression that you should also take the sum of their complexities (unless you have a precise definition of what "sum of problems" means and you do not confuse this definition with the usual sum of numbers, of course). $\endgroup$
    – timur
    Jan 1, 2011 at 22:11
  • 1
    $\begingroup$ Agree with timur, seems like the problem is not about what the Omega will be if we can add the sub-problem sizes, but about whether we can even add them at all, or even if you can claim Omega for each independent sub-problem. Would you care to elaborate exactly what your proof was and what the objections were? $\endgroup$
    – Aryabhata
    Jan 2, 2011 at 4:09
  • 1
    $\begingroup$ @Alon: Not sure which comment you are referring to. None of the above comments mentions BigOh. $\endgroup$
    – Aryabhata
    Jan 3, 2011 at 5:40

2 Answers 2

6
$\begingroup$

Your original reasoning is indeed problematic, since you're adding together a variable number of things. Suppose you have $n$ subproblems, each of which takes constant time; can you conclude that the whole thing is $O(n)$, or $\Omega(n)$? No, since the constants may vary: the $i$th subproblem may take time $1/i$, or $i^3$; each is still a constant (independent of $n$), but their sum could be a constant, or grow with $n$ - you can't tell. It depends on the distribution of the constants, and that's something the notation $O$ and $\Omega$ conceals (deliberately, of course).

However, as Moron pointed out, adding together just two (or any constant number) of functions is fine. Thus I'm not sure I understand the TA's claim.

$\endgroup$
15
  • $\begingroup$ Hi @Alon, thanks for the answer. I'm not sure where Moron's answer went to, though I saw it for a few minutes before I went to bed. In my case, we actually knew that the subproblems were identically sized, so the constant (whatever it was) was the same. $\endgroup$
    – dsolimano
    Jan 1, 2011 at 14:10
  • $\begingroup$ $\mathcal{O}(.)$ and the other symbols denote classes of functions. There is indeed no $+$ defined on sets of functions (that I knew of); its common use is abuse of notation. $\endgroup$
    – Raphael
    Jan 1, 2011 at 16:51
  • 1
    $\begingroup$ @Alon: If the $i^{th}$ sub-problem constant is $i^3$, then it is not really a 'constant'! $\endgroup$
    – Aryabhata
    Jan 1, 2011 at 17:47
  • 1
    $\begingroup$ @Alon: The constant of the last subtask is $n^3$ for instance. $\endgroup$
    – Aryabhata
    Jan 2, 2011 at 7:57
  • 1
    $\begingroup$ @Alon: Suppose I had an algorithm which given an array of size $n$, split into tasks of size 1 to n, each of which found the minimum of the first i elements. According to your logic, each sub-task is O(1)! $\endgroup$
    – Aryabhata
    Jan 3, 2011 at 5:39
2
$\begingroup$

What you need to be talking about is $\displaystyle \Omega(f+g)$ and not $\Omega(f) + \Omega(g)$ as $\Omega(f)$ and $\Omega(g)$ are sets.

If $\displaystyle |h(x)| \ge c_1 |f(x)|$ and $\displaystyle |h(x)| \ge c_2 |g(x)|$ then we have that

$\displaystyle |h(x)| \ge \frac{c}{2} (|f(x)| + |g(x)|) \ge c' |f(x) + g(x)|$, where $\displaystyle c = \text{min}\{c_1, c_2\}$.

Thus if $\displaystyle h \in \Omega(f)$ and $\displaystyle h \in \Omega(g)$, then $h \in \Omega(f+g)$.

But in your case, even though you have a variable number of sub-problems, I am not really sure I completely agree with Alon.

It really depends on what you consider to be variable when you consider each sub-problem.

If $n,k$ are the variables, and you have a a constant $c$ (independent of $n$ and $k$) such that each of the $\frac{n}{k}$ independent sub-problems is of size at least $c k \log k$, then you can add them up the way you did, to get the total size.

For instance consider the problem where an array is almost sorted: each element is within $k$ of its original position. You can sort the array by sorting $\frac{n}{k}$ chunks of $2k$ elements each. If you wanted to consider the total time taken, say with the algorithm you picked for sorting, each chunk always takes $\Omega(k\log k)$ time, then the total time is indeed $\Omega(n \log k)$.

If you had the $i^{th}$ subproblem constant, be a function of $i$, then it is not really a constant, as it depends on $\frac{n}{k}$.

Now if you allowed the $i^{th}$ sub-problem constant to be independent of $k$, but not $n$, then adding them up becomes kind of meaningless and could lead to incorrect results, as Alon noted.

Note: If you were trying to prove an $\Omega(n \log k)$ lower bound for sorting in the above problem, by considering $n/k$ sub-problems of size $k$, just adding like that is not a proof of overall lower bounds. In the worst case, each sub-problem could be $\Omega(k \log k)$, but when you hit the worst case for one sub-problem, you might be hitting the best case for another. So even claiming $\Omega(k \log k)$ lower bounds for each sub-problem needs more proof.

You could add up for the upper bounds though. You can say that an algorithm would be $\mathcal{O}(n \log k)$ in the worst case (for instance, if you picked heap-sort), even though some sub-problem might take $\mathcal{o}(k \log k)$ comparisons (note: small oh), the total number of comparisons is essentially $\mathcal{O}(n \log k)$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .