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.

1) If $a(n)=O(n^2)$ and $b(n)=O(n^3)$. Can someone tell me how to compute the computational complexity of

$$ c(n)=\sum_{k=1}^{n}a(k)b(k) $$

What rules apply?

I think it might be $O(n^6)$, but this sounds wrong.

2) What now if we have two sums. Suppose $a(n)=O(n^2)$ and $b(n)=O(1)$ and $c(n)=O(1)$ what would the computational complexity of something like this

$$ d(n)=\sum_{k=0}^{n}\sum_{j=0}^{k}c(n-k)b(k-j)a(j) $$

be? I would really like to know how to compute the computational complexity of such types of sums. Any pointers would be appreciated.

share|improve this question
    
You might want to consider posting this on stackoverflow, one of Math.Stackexchange's sister sites that specializes in computer science. While your question isn't off topic, it might elicit a better response there. –  Sam DeHority Jan 26 '13 at 23:44
    
@DoctorBatmanGod There is also cs.stackexchange.com that can help with time complexity of algorithms. –  OghmaOsiris Jan 26 '13 at 23:45
    
For the first one the worst case is when $a(n)=\Theta(n^{2}),b(n)=\Theta(n^{3})$. without loss of generality $a(n)=n^{2},b(n)=n^{3}$. Then bound the sum you have in terms of $n$. For example each element is $\leq n^{6}$and since there are $n$ terms a bound is $n\cdot n^{6}=n^{7}$. But with a more careful analysis you can get this down and get a better upper bound. –  Belgi Jan 26 '13 at 23:45
1  
@DoctorBatmanGod - Since there is even no code/algorithm in the question I would say that this is the best site for this question –  Belgi Jan 26 '13 at 23:46

1 Answer 1

up vote 1 down vote accepted

For your first question, say $a(k)\le Mk^2$, $b(k)\le Nk^3$. Then your sum is $\le MN(1^5+2^5+\cdots+n^5)$. For large $n$, the sum $1^5+2^5+\cdots+n^5$ behaves like $\frac{1}{6}n^6$. So the $O(n^6)$ is correct.

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.