GATE: Algorithms (Source: StackOverflow)

Question

Answer 1

O(n^2)

Comments

How n + n + n + .........+ n is n^2 it should be n^n?

---

Let us say we take out n common then it would be n (1 + 1 + … n times) = n x n = n^2 (powers get added).

Note: n * n * n * n …. n times = n^n. (if you multiply n, n times then it would be n^n. But above we have added).

---

 

Can you recheck on this statement pls? with n>4.3 billion, that sum is approaching towards 2 and not 1. With big enough n, sum always reaches 2

Also check if it shouldn't be $n+n+n+n...+n$, rather $n^{1 + 1/2 + 1/4 + 1/8 + ...}$ $\approx$ $n^2$