Teaching Kids Programming: Videos on Data Structures and Algorithms
Let’s compute the following:
Math Proof of the Equation of Sum of the First N Positive Integers
We know that the sum of the first few positive integers is:
Let’s write it again but in backwards order:
Therefore,
And
So we have
Compute Sum of 1/(1+2+..N) Using Math and Python
Therefore, we can rewrite the above:
Thus, the intermediate terms are canceled out.
Thus, we can implement in Python:
1 2 | def f(N): return 2 - 2/(N+1) |
def f(N): return 2 - 2/(N+1)
Alternatively, we can iterate over each term and sum it up (Brute Force Algorithm):
1 2 3 4 5 | def f(N): ans = 0 for i in range(1, N+1): ans += 2.0 / i*(i+1) return ans |
def f(N): ans = 0 for i in range(1, N+1): ans += 2.0 / i*(i+1) return ans
Clearly, the first approach is O(1) constant as it just computes a math equation, and the second method is O(N) linear as it needs to process and sum up N terms.
–EOF (The Ultimate Computing & Technology Blog) —
GD Star Rating
loading...
794 wordsloading...
Last Post: Unleashing Innovation: Inside Hackathon Events at Big Internet Companies (Hackathon T-shirt from Microsoft)
Next Post: How to Transfer or Send ETH to Another Wallet on Ethereum Blockchain?