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!!

ford prefect · Accepted Answer · 2014-11-11 15:50:02Z

6

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.

answered Nov 11, 2014 at 15:50

ford prefect

7,41611 gold badges60 silver badges85 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Analyzing General Algorithm Complexity

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related