0

What would be the big o for the algo:

for (i=0; i < n*n; i++)
  for(j=0; j<i*i; j++)

As per my understanding
1st loop will loop upto n2 times.
2nd loop will go around n2 times.

Am I right or is it a O(n6) representation?

Also is there a easy way to say when to use log. I have assumed that whenever the loop variable is multiplied the ln function is applied

e.g.: for (i=1; i<n*n i=i*2) Big o for the loop as per my understanding is O(ln n2) (Am I right again?)

1
  • What does the log have to do with it? Oct 8, 2014 at 1:54

1 Answer 1

2

These are 2 distinct questions.

1) Yes, this is O(n^6). You can, in fact, directly compute the number of iterations, inner loop makes i^2 iterations, so sum i^2 for i from 0 to n^2. Input this into Wolfram Alpha or Matlab and you get 1/6 * n^2 * (n^2 + 1) * (2 * n^2 + 1)

2) That is a useful mnemonic. Yes, a log naturally arises when you count the number of times you need to multiply something by itself to get something else. That is not the only place it arises though. Also, O(ln(n^2)) = O(2 * ln(n)) = O(ln(n))

4
  • what other places do log arise? sorry if this question is too naive
    – new
    Oct 7, 2014 at 18:00
  • Pure log? I don't remember any cases off the top of my head. However sorting takes a minimum of n*log(n) in worst case and the log there is far from trivial (That actually arises from the quotient of factorial and 2^n)
    – Ordous
    Oct 7, 2014 at 18:04
  • @Ordous: only if you are sorting by comparison. Oct 7, 2014 at 18:16
  • @kevincline Yeah, I forgot there are other ways, thank you.
    – Ordous
    Oct 7, 2014 at 18:20

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.