Summation of $O(n)$ from $1\le k\le n$.
I think it should be $O(n)$ only. Because we are addition $O(k)$ and maximum order will be $O(n)$. But answer is given as $O(n^2)$.
Correct me if I'm wrong.
Tell me more
×
Computer Science Stack Exchange is a question and answer site for
students, researchers and practitioners of computer science. It's 100% free, no registration required.
|
|
|||||||||||
|
|
I think I understood you from your comments above. I think you have issues in the very basics of complexity analysis. I think what you want to say is that you are summing the term $O(n)$, $O(k)$ times for $1 \leq k \leq n$ . right? In this case, the answer is $O(nk)$. If $O(k) \in O(n)$ (for example $k = n/c$ for $c \in O(1)$) then, then the answer is $O(n^2)$. is that what you want ? Comment I see from the comments $k = 3$. Therefore, I can understand $k$ is constant and $O(k) \in O(1)$. Therefore $O(kn) \in O(n)$. This is why you get $O(n)$, while you are confused with $O(n^2)$. But for instance, if k = n * (some weird constants) = 3, then badly your solution is $O(n^2)$. Example: Assume that your program requires $k$ functions, each of with requires $O(1)$ (that is, no matter what size of input you got (i.e. $n$) it will always take $O(1)$ time units to run a function). In this case, your total is $O(k)$. The number of functions in your program also does not depend on the number of $n$. It is also constant (that is, $O(1)$). Therefore, the total running time of your program is $O(1)$ ! If the functions above required $O(n)$ execution time complexity, then similarly it is $O(n)$.. This is all because $k$ is constant. Even if $k = 10^6$ and your input was of size $n = 100$. The same bound remains. Why ? because one day, you will run an input of size $n = 10^{1000}$, but $k$ remains to be $10^6$. One example commonly found. Assume we have a graph $G = (V, E)$ constructed in a way such that each vertex $v$ is connected to $d$ other vertices. In this case $0 \leq d \leq n - 1$. Therefore, the number of edges of the graph $|E| = (\sum _{v \in V} d) / 2 = nd /2$. If $d$ is fixed (let's say to exactly 4), then $|E| \in O(n)$. However, assume that $d$ is a function of $n$. For instance, a vertex $v$ select $1/2$ of the other vertices as neighbors. Therefore, $d = \frac{1}{2}(n-1)$. In this case $|E| = nd/2 = n (\frac{1}{2}(n-1)) \in O(n^2)$. In the first case (i.e. $|E| \in O(n)$), the graph is sparse. In the other case, the graph is dense. |
||||
|
|
Suppose $T_n = O(n)$. That means that for some constant $C$, $T_n \leq Cn$. Therefore $$ \sum_{m=1}^n T_m \leq C \sum_{m=1}^n m = \frac{C}{2} m(m+1) = O(m^2). $$ If also $T_n = \Omega(n)$ then you can show in exactly the same way that the sum is $\Omega(n^2)$, so that no better bound is possible (for concreteness, you can take $T_n = n$). |
|||||||||||
|
|
There's no correct answer unless you specify what the $n$ functions are. For example, consider, for each $k$, the function $f_k(n) = kn$. For any fixed $k$, $f_k(n) \in O(n)$. Yet $\sum_{k=1}^{n} f_k(n) = \sum_{k=1}^n kn = n\frac{n(n+1)}{2} \in O(n^3)$. A different choice of sequence $f_k$ could yield just about any function in $\Omega(n)$. So we can take a sequence of $k$ functions, each of which is $O(n)$, and sum them to get a function that's $O(n^3)$ (for instance). If you have a single fixed function $f(n) \in O(n)$, then of course $\sum_{k=1}^n f(n) = nf(n) \in O(n^2)$. |
||||
|
|
