performance - how i calc the time complexity in python code? - Stack Overflow
python - Is there a tool to automatically calculate Big-O complexity for a function - Stack Overflow
python - How do I calculate Time Complexity for this particular algorithm? - Stack Overflow
calculation time complexity and space complexity
Videos
Hi,
I was learning about sorting algorithms and came across the terms time complexity and space complexity for a Python code.
Please have a look here: https://imgur.com/a/SHFko7P
Source for Figure #1: https://www.geeksforgeeks.org/sorting-algorithms-in-python/
Source for Figure #2: https://www.simplilearn.com/tutorials/data-structure-tutorial/time-and-space-complexity
Question: How do they plot the graph shown in Figure #2? What kind of formula did they use? Likewise, how did they calculate Big O notation in Figure #1? Could you please guide me?
First, a few hints:
- In your code there is no nested loop. The
if-statement does not constitute a loop. - Not all nested loops have quadratic time complexity.
- Writing
O(n) = N*Ndoesn't make any sense: what isnand what isN? Why doesnappear on the left butNis on the right? You should expect your time complexity function to be dependent on the input of your algorithm, so first define what the relevant inputs are and what names you give them. - Also,
O(n)is a set of functions (namely those asymptotically bounded from above by the functionf(n) = n, whereasf(N) = N*Nis one function. By abuse of notation, we conventionally writen*n = O(n)to meann*n ∈ O(n)(which is a mathematically false statement), but switching the sides (O(n) = n*n) is undefined. A mathematically correct statement would ben = O(n*n). - You can assume all (fixed bit-length) arithmetic operations to be O(1), since there is a constant upper bound to the number of processor instructions needed. The exact number of processor instructions is irrelevant for the analysis.
Let's look at the code in more detail and annotate it:
a, b = map(int, input().split()) # O(1)
list = [] # O(1)
for i in range(1, a+b+1): # O(a+b) multiplied by what's inside the loop
if a % i == 0 and b % i == 0: # O(1)
list.append(i) # O(1) (amortized)
n = len(list) # O(1)
print(list[n-1]) # O(log(a+b))
So what's the overall complexity? The dominating part is indeed the loop (the stuff before and after is negligible, complexity-wise), so it's O(a+b), if you take a and b to be the input parameters. (If you instead wanted to take the length N of your input input() as the input parameter, it would be O(2^N), since a+b grows exponentially with respect to N.)
One thing to keep in mind, and you have the right idea, is that higher degree take precedence. So you can have a step that’s constant O(1) but happens n times O(N) then it will be O(1) * O(N) = O(N).
Your program is O(N) because the only thing really affecting the time complexity is the loop, and as you know a simple loop like that is O(N) because it increases linearly as n increases.
Now if you had a nested loop that had both loops increasing as n increased, then it would be O(n^2).