If i have the following code
def func(A,n):
for i in A-1:
for k in A-1:
for l in A-1
if A[i]+A[k]+A[l] = 0:
return True
else:
return False
How can i analyze the run time for this algorithm? As i see it every for loop has 2 units, and each loops runs n+1 times. the if loop then runs 3*n time, with 3 units. Then each return is one, however only on of them will run, so in total it will amount to something like
T(n) = 2(n+1)+2(n+1)+2(n+1)+3(n)+1 = 9n+7
Is my logic correct or am i missing something. Also could the runtime vary from language to language?
As the comments said, the code as is now is O(1) since it will exit out of func after a single pass every time.
If you did change the returns to something else, like setting a variable, then it would become O(n^3).
To explain how you get to that value, I'm going to reduce the problem to two loops:
def func(A,n):
for i in A-1:
for k in A-1:
# Do Something else
If you think about what this is doing, for each value of i we iterate through, we will execute A-1 times to get through the k loop.
i=0, k=0
i=0, k=1
...
i=0, k = A-1
So this goes on for A-1 or n cycles. Then,
i=1, k=0
i=1, k=1
...
i=1, k=A-1
This also goes on for n cycles. See the pattern? For each value of i we will iterate n times. Now, this will keep on going until we exhaust all the values of i which we know is also A-1 or n times. Thus, the run time for this function will be O(n^2).
The worse case runtime (big-O) will not vary programming language to programming language strictly speaking. Of course, each programming language has different levels of optimization and will execute in different lengths of time, but strictly considering algorithm cycles they will be the same.