Python Algorithm Analysis

Question

Determine the exact number of times BigFn() is called.

for i in range(1,N+1):
   for j in range(1,N*N+1):
      myList[i][j] = BigFn(i,j)

This is what I'm guessing.

for i in range(1,N+1): # N times
   for j in range(1,N*N+1): # N^2 times
      myList[i][j] = BigFn(i,j) #Here is where I don't know what to do...?

And how do I figure out the best and worst case behaviour?

Thanks in advance!

We also don't know. What does BigFn do?

nhahtdh
– nhahtdh

2014-11-04 05:37:35 +00:00
Commented Nov 4, 2014 at 5:37 — nhahtdh
– nhahtdh, Commented Nov 4, 2014 at 5:37
Sorry I fixed the question. How many times is BigFn called.

Murray S
– Murray S

2014-11-04 05:40:04 +00:00
Commented Nov 4, 2014 at 5:40 — Murray S
– Murray S, Commented Nov 4, 2014 at 5:40

Lrrr · Accepted Answer · 2015-01-05 11:41:14Z

3

your guesses are correct and bigFn() is called O(n³) times. As you said :

for i in range(1,N+1): # N times
   for j in range(1,N*N+1): # N^2 times

so based on rule of product, BigFn() is called O(n³) times.

edited Jan 5, 2015 at 11:41

answered Nov 4, 2014 at 5:41

Lrrr

4,8055 gold badges44 silver badges65 bronze badges

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

4 Comments

Murray S Over a year ago

How did you figure that out?

Lrrr Over a year ago

@MurrayS it is very basic mathematics, and it called rule of product.

Murray S Over a year ago

That's for changing your answer. And would there be anyway to find out best case behaviour and worst case behaviour?

Lrrr Over a year ago

There is no best case or worst case, best case and worst case have a meaning when behavior may change regarding to input, but in your case, you always iterate between 1 to n+1 and 1 to n*n + 1. so there is no best case or worst case, bigFn is always called O(n^3).

Collectives™ on Stack Overflow

Python Algorithm Analysis

1 Answer 1

4 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

4 Comments

Your Answer

Sign up or log in

Post as a guest

Related