0

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!

2
  • 1
    We also don't know. What does BigFn do?
    – nhahtdh
    Nov 4, 2014 at 5:37
  • Sorry I fixed the question. How many times is BigFn called.
    – Murray S
    Nov 4, 2014 at 5:40

1 Answer 1

3

your guesses are correct and bigFn() is called O(n3) 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(n3) times.

4
  • How did you figure that out?
    – Murray S
    Nov 4, 2014 at 5:43
  • 1
    @MurrayS it is very basic mathematics, and it called rule of product.
    – Lrrr
    Nov 4, 2014 at 5:45
  • That's for changing your answer. And would there be anyway to find out best case behaviour and worst case behaviour?
    – Murray S
    Nov 4, 2014 at 5:46
  • 1
    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).
    – Lrrr
    Nov 4, 2014 at 5:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.