✅ Algorithm analysis
Can someone help me understand how we got this formula to calculate time efficiency from this code?
this is the formula: f(n) = n2/2 + n/2, which is O(n2)
The formula goes like this, 1 + 2 + 3 + 4 + ... + N but i have no idea how to connect the dots. Thanks!
7 Replies
im really not sure that the formula is correct
if im calculating correctly it should be O(n*(n/2))
aka O(n^2)
f(n) = n^2/2 + n/2, which is O(n^2)
Sorry this is the formula! Didnt type it properly
ah ok
Can you please walk me through how you arrived at that formula?
im still not sure that this is completelly correct, but close enough
sure
so you have the outer loop, if you had only that, it would be O(n), right
and for every i you go from 1 to i in the second loop
for i = 1 thats 1 for i = 2 thats two for i = n thats n
if you take average of the numbers you get n/2
and thats what im multipling the first n, because on average you go n/2 for each i
so you get O(n*(n/2)) which is essentially O(n^2)
Ahhhhhh I see.. Got it now thank you sir 🙂
np