Analyzing General Algorithm Complexity

Question

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 overall time complexity would be O(n)+O(n^2) = O(n^2) time.(Is this right ??)

Also the space complexity would be O(n) as we have n blocks in memory to store n elements(Is this right ??) Is this the correct way to analyze the run time and space complexity?.I can analyze the time complexity of common sort algorithms and data strutures but Im having a bit of difficulty analyzing it just for a general program.Thanks!!

Answer 1

This is going to be O(n^2) as n grows n^2 will dwarf the O(n) section so that part drops 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 time calculating will be spent on the second operation. As n increases the second operation will continue to dominate. I see no reason it wouldn't be O(n) space complexity.