Ruby:
Java:
- Started reading Data Structures and Abstraction in Java's section about big O notation. So far they seem to do a better job of explaining than either of the other two resources I used. One thing I really liked about it was that when they introduced the concept of algorithms of varying efficiency to accomplish the same task, they gave examples and then broke those examples down into their speeds based on the number of calculations done.
- I still don't quite understand how they got n(n+1)/2 as the number of additions in the algorithm:
sum = 0 for i = 1 to n { for j = 1 to i sum = sum + 1 } - Mainly, I don't really understand how they are calculating this. I guess the first n would come from the exterior loop, but how is the (n+1)/2 calculated?
Here is the same program in Python:
ReplyDeleten = 10
sum = 0
for i in range(1, n+1):
for j in range(1, i+1):
sum += 1
print(sum)
It prints 55, which is indeed 10 * 11 / 2
Now as to why, think about it this way.. It is an O(n**2) algorithm, since it is looping over n things, n times. But actually, the inner loop runs n times at most, and only 1 time in the least case.
That's n + (n - 1) + (n - 2) + ... + 2 + 1
Now to simplify this sum added it to itself in reverse order:
n + (n - 1) + (n - 2) + ... + 2 + 1
1 + 2 + 3 + ... + (n - 1) + n
-----------------------------------------------------------------
(n + 1) + (n + 1) + (n + 1) + ... (n + 1) + (n + 1)
That's n * (n +1), but since we counted each term twice, its n * (n + 1) / 2