JustPaste.it - Share Text & Images the Easy Way

A geometric series is the sum of the numbers in a geometric progression

general geometric series formula :
formula

you can derive from the formula :

$a(r^{0} + r^{1} + r^{2} + r^{3} + ... + r^{n-1})$

and it's exactly same as the pattern we got when calculating complexity of nested loops:

${\color{Blue} n(\frac{1}{5^{k-1}} + ... + \frac{1}{5^{2}} + \frac{1}{5^{1}} + \frac{1}{5^{0}})}$

we can write this pattern as :

${\color{Blue} n((\frac{1}{5})^{0} + (\frac{1}{5})^{1} + (\frac{1}{5})^{2} + ... + (\frac{1}{5})^{k-1})}$

${\color{Blue} \sum_{i=0}^{k-1} n(\frac{1}{5})^{i}}$ ${\color{Blue} = O(n)}$

you can conclude from this sum formula that time complexity is O(n).