0

I'm having trouble understanding how to analyze these two series for their Big O representations.

I can get the correct answer for this series

$1+2+3+4+...+N$ is $O(N^2)$, which I found by finding the Big O for the equation $N(N+1)/2$.

Apparently the correct answer for the following question is $O(N)$, but my result obviously differs substantially.

$1+5+25+125+...+N$ is $O(5^N)$

I figured that since the series equation is just $(5^N-1)/4$, I can just find the Big O for that equation, which would be $O(5^N)$

Where is my understanding here flawed?

cdignam
  • 575

1 Answers1

1

Note that the last element in your sum is $N$ rather than $5^N$. So, writing $N=5^k$, the sum is $1+5+\cdots+5^k$, which is $O\left(5^k\right)$ as you wrote; but $5^k=N$, so the sum is $O(N)$.

Guy
  • 2,414
  • Would that mean that the first series I mentioned, $1+2+3+4+...+N$ is not* $O(N^2)$, but simply, $O(N)$? – cdignam Oct 23 '16 at 21:56
  • I think you are correct, but I'm not sure I understand your reasoning. The way I have it, N is the value to the i-th element, so, while the equation may be $(5^i-1)/4$, the Big O would be different. $i=log_5(N)$, which I then plug into the equation to get $(5^{log_5(N)}-1)/4$, more simply, $(N-1)/4$, which is of the order $O(N)$, as you said. – cdignam Oct 23 '16 at 22:22
  • @cdignam The first sum is not the same. Here, we expect the last element to be $N$, unlike the second sum where we expect $5^k$. Plus, the formula you wrote for the first sum is OK, so it's $O(N^2)$. – Guy Oct 24 '16 at 07:21