Analysis of the total complexity of the algorithm
Assuming I have a program like this:
def fn(array,num):
for i in range(0,len(array)):
if(i==num):print i
for i in range(o,len(array)):
for j in range(0,i):
if(i*j==num):print i,j
So the first loop runs in O (n) time. The second loop runs in O (n * n) time.
The total time complexity will be O (n) + O (n ^ 2) = O (n ^ 2) (is that correct?)
Also, the space complexity would be O (n), since we have n blocks in memory to store n elements (is that correct?) Is this the right way to analyze runtime and spatial complexity? I can analyze the time complexity of general sorting algorithms and data, but I have a bit of complexity analyzing this for a general program only. Thank!
source to share
It will be O (n ^ 2) as n grows n ^ 2 will eclipse the O (n) section for the part to fall out. For example, when n is 100. The first operation will take 100 units of time, and the second will take 10,000 units. 99% of the calculation time will be spent on the second operation. As n grows, the second operation will continue to dominate. I see no reason why this wouldn't be O (n) complexity.
source to share