def Arithmetic (n):
for i in range (1, n):
for j in range (1, (i + 1) / 3):
a = n^i - j/3
return a
How do I determine the Big O for this algorithm? Given that the second loop has a maximum with the first loop result.
It's O(n^2). Big-O doesn't track runtime. It tracks how much the runtime changes as the size of the input changes. Your runtime here is very similar to Selection Sort, which runs on a slightly smaller section of the list each time:
n + (n-1) + (n-2) + (n-3) + (n-4) + ...
Selection Sort is known as one of the O(n^2) sorting algorithms, meaning that as its input gets bigger linearly, its runtime increases quadratically.
Your function is like that. See the same pattern:
n/3 + (n-1)/3 + (n-2)/3 + ... = 1/3 * (n + (n-1) + (n-2) + ...)
Since big-O notation ignores the factor 1/3, it's evident your function is O(n^2). Its runtime will increase quadratically as the size of the input increases linearly.
(as a sidenote, you need to rework what's happening with a in your algorithm. The way you have it, it's just getting overwritten constantly. You might want to set it to 0 at the beginning, and change the other line to have += or something instead of =.