Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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? –  timur Jan 1 '11 at 20:00
    
@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. –  dsolimano Jan 1 '11 at 21:15
1  
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). –  timur Jan 1 '11 at 22:11
1  
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? –  Aryabhata Jan 2 '11 at 4:09
1  
@Alon: Not sure which comment you are referring to. None of the above comments mentions BigOh. –  Aryabhata Jan 3 '11 at 5:40

2 Answers 2

up vote 6 down vote accepted

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.

share|improve this answer
    
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. –  dsolimano Jan 1 '11 at 14:10
    
$\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. –  Raphael Jan 1 '11 at 16:51
1  
@Alon: If the $i^{th}$ sub-problem constant is $i^3$, then it is not really a 'constant'! –  Aryabhata Jan 1 '11 at 17:47
1  
@Alon: The constant of the last subtask is $n^3$ for instance. –  Aryabhata Jan 2 '11 at 7:57
1  
@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)! –  Aryabhata Jan 3 '11 at 5:39

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)$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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