# How to compute the complexity

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.

-
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
@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

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.