Teaching Kids Programming: Videos on Data Structures and Algorithms
The Sum of First N Odd Numbers goes like this 1, 1+3=4, 1+3+5=9, 1+3+5+7=16 … As we can guess the sum of the first N Odd numbers is equal to N squared.
Sum of First N Odd Numbers using Loop
We can accumulate each odd numbers:
1 2 3 4 5 | def sumOfOdd(N): ans = 0 for i in range(1, 2*N, 2): ans += i return ans |
def sumOfOdd(N): ans = 0 for i in range(1, 2*N, 2): ans += i return ans
This takes O(N) time, and O(1) space.
Sum of First N Odd Numbers using Math Induction
Proposition: f(N) is the sum of the first N Odd Numbers and it is equal to N^2.
Base case: When N is 1, f(1) = 1 which is correct as the only odd number here is one.
Assume, N=K, f(N), and if we add one more odd number, which is 2*K+1, thus:
therefore
By using Math induction, we have proved the sum of first N Odd Numbers is N^2.
Implementation of such is trivial:
1 2 | def sumOfOdd(N): return N * N |
def sumOfOdd(N): return N * N
The time complexity is O(1) constant, and the space complexity is also O(1). How about Sum the Even Numebrs? Teaching Kids Programming – Sum of First N Even Numbers (with Mathematic Induction)
–EOF (The Ultimate Computing & Technology Blog) —
loading...
Last Post: Parentheses Grouping Algorithm
Next Post: Algorithm to Make a List Equal with Increments