12 Replies - 3037 Views - Last Post: 26 January 2013 - 01:12 PM

#1 antolin  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 2
  • Joined: 25-January 13

big O exponential

Posted 25 January 2013 - 02:47 AM

Hi Gurus,

I am a newbie here, and also a newbie to Big O notation, I have read KYA's very informative and easy to understand tutorial on Big O, however I am still having some questions in my head. Such as how can exponential big O such as O(K^n) where K is constant and n is the size happen in a simple for loop code.

Secondly, if I have a for loop like this

for(int a=1; a<n; a*=2)  [i]//this will give O(log n) as I understood from Kya's tutorial[/i]
        {
            for(int b=1; b<n; b++) [i]//each of the nested for loops will be n and a total of three will mean O(n^3)[/i]
            {
                for(int c=1; c<n; c++)
                {
                    for(int d=1; d<n; d++)
                    {
                    }
                }
            }
        }

so does it mean that O(log n * (n * n * n)) equals to O(log n^4)

Lastly, If I have a for loop such as the following

for(int i = 0; i < n*n; *= 2) {
	for(int j = 0; j < i*i; *= 3){
		//content running in constant time
	}
}

would it be
first loop: ((log n)*(n*n)) * second loop: ((log n) * (n*n)) equals to O(log n^3)^2 ?

I hope the gurus here would address all of my 3 questions as I have been trying to understand this Big O thoroughly and not just on the surface.

This post has been edited by blackcompe: 25 January 2013 - 06:13 AM
Reason for edit:: [code] tags


Is This A Good Question/Topic? 0
  • +

Replies To: big O exponential

#2 blackcompe  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 1155
  • View blog
  • Posts: 2,533
  • Joined: 05-May 05

Re: big O exponential

Posted 25 January 2013 - 06:36 AM

Quote

so does it mean that O(log n * (n * n * n)) equals to O(log n^4)


If I'm not mistaken it's:

for(int a=1; a<n; a*=2) //O(log(n))
     for(int b=1; b<n; b++) //O(n)
          for(int c=1; c<n; c++) //O(n)
               for(int d=1; d<n; d++) //O(n)
                    ;



The algorithm in total is O(log(n)) * O(n) * O(n) * O(n) = O(n3log(n))

Quote

would it be
first loop: ((log n)*(n*n)) * second loop: ((log n) * (n*n)) equals to O(log n^3)^2 ?


for(int i = 0; i < n*n; *= 2) //O(log(n^2))
     for(int j = 0; j < i*i; *= 3) //O(log^2(n^2))
          ;



I think the inner loop is actually log3, but for simplicity we'll assume it's log2 (and therefore a looser bound). The algorithm in total is then O(log(n2)) * O(log2(n2)) = O(log3(n2))

This is my best effort guess. Maybe someone can confirm or disaffirm its correctness.

This post has been edited by blackcompe: 25 January 2013 - 06:50 AM

Was This Post Helpful? 2
  • +
  • -

#3 sepp2k  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 2113
  • View blog
  • Posts: 3,234
  • Joined: 21-June 11

Re: big O exponential

Posted 25 January 2013 - 08:33 AM

View Postantolin, on 25 January 2013 - 10:47 AM, said:

Such as how can exponential big O such as O(K^n) where K is constant and n is the size happen in a simple for loop code.


Most trivially by explicitly looping from 0 to K^n for some K. For example this loop would have a O(2^n) runtime:

int limit = pow(2, input.size());
for(int i = 0; i < limit; i++) {
  // Do something that takes constant time
}



A real world scenario where you might write code like this is if you wanted to iterate all possible subsets of a list.

Quote

so does it mean that O(log n * (n * n * n)) equals to O(log n^4)


No, it doesn't. x log y (or (log y) * (x), which is the same thing of course) is not the same thing as log (x*y). Your code is (log n) * (n * n * n), which can be more succinctly written as n^3 log n. It's not log n^4.

Quote

Lastly, If I have a for loop such as the following

for(int i = 0; i < n*n; *= 2) {
	for(int j = 0; j < i*i; *= 3){
		//content running in constant time
	}
}

would it be
first loop: ((log n)*(n*n)) * second loop: ((log n) * (n*n)) equals to O(log n^3)^2 ?


Actually that's an infinite loop because 0*2 is still 0. So I'll assume that i and j actually start at 1 (and that *= 2 and *= 3 actually read i *= 2 and j *= 3 respectively).

If you're iterating from 1 to some value x by doubling the value of x at each iteration, you need log x steps. In your case x is n^2 so the outer loop is log n^2. The inner loop is log i^2, so if we consider that the upper bound for i is n^2 we know that the inner loop is O(log (n^2)^2) = O(log n^4). That would make the whole loop O((log n^2) * (log n^4)). However I'm not sure whether that's also its big-Theta.

View Postblackcompe, on 25 January 2013 - 02:36 PM, said:

I think the inner loop is actually log3, but for simplicity we'll assume it's log2 (and therefore a looser bound).


The base of a logarithm is simply a constant factor, so there's no difference between log_2 and log_3 in Big-Oh analysis.

Quote

The algorithm in total is then O(log(n2)) * O(log2(n2)) = O(log3(n2))

This is my best effort guess. Maybe someone can confirm or disaffirm its correctness.


How did you get log^2(n^2) for the inner loop.
Was This Post Helpful? 2
  • +
  • -

#4 mojo666  Icon User is offline

  • D.I.C Addict
  • member icon

Reputation: 352
  • View blog
  • Posts: 771
  • Joined: 27-June 09

Re: big O exponential

Posted 25 January 2013 - 10:39 AM

View Postsepp2k, on 25 January 2013 - 03:33 PM, said:

How did you get log^2(n^2) for the inner loop.

I suspect he meant this for the whole answer, then multiplied by the outer loop an extra time. It's slightly more accurate than your answer.

log(a^c) = c*log(a)

So, if a=n^2, then your answer was log(a)*log(a^2) = 2*log(a)*log(a) = 2*log^2(n^2). This is O(log^2(n^2))
But, using the same logic, we can make it even more accurate by getting rid of the exponent in n^2 and just have O(log^2(n))

This post has been edited by mojo666: 25 January 2013 - 10:44 AM

Was This Post Helpful? 3
  • +
  • -

#5 blackcompe  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 1155
  • View blog
  • Posts: 2,533
  • Joined: 05-May 05

Re: big O exponential

Posted 25 January 2013 - 11:11 AM

Quote

How did you get log^2(n^2) for the inner loop.


Since i's upper bound is O(log(n2)), and the inner loop condition is j < i*i, you get O(log2(n2)) for the inner loop.

Note that log(n4) = log2(n2), so our answers are the same.

Quote

The base of a logarithm is simply a constant factor, so there's no difference between log_2 and log_3 in Big-Oh analysis.


Ah, good to know.

This post has been edited by blackcompe: 25 January 2013 - 11:27 AM

Was This Post Helpful? 1
  • +
  • -

#6 mojo666  Icon User is offline

  • D.I.C Addict
  • member icon

Reputation: 352
  • View blog
  • Posts: 771
  • Joined: 27-June 09

Re: big O exponential

Posted 25 January 2013 - 12:52 PM

View Postblackcompe, on 25 January 2013 - 06:11 PM, said:

Since i's upper bound is O(log(n2)), and the inner loop condition is j < i*i, you get O(log2(n2)) for the inner loop.


Ah, so that's how you got it. i's upper bound is n^2, not log(n^2). The inner loop is O(log(i*i)). If i's upperbound was log(n^2), this would be O(log(log^2(n^2))). With it's actual upper bound, the inner loop is O(log(n^2 * n^2)) and as previously shown the whole algorithm is O(log^2(n)).
Was This Post Helpful? 0
  • +
  • -

#7 blackcompe  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 1155
  • View blog
  • Posts: 2,533
  • Joined: 05-May 05

Re: big O exponential

Posted 25 January 2013 - 02:55 PM

Quote

Ah, so that's how you got it. i's upper bound is n^2, not log(n^2). The inner loop is O(log(i*i)). If i's upperbound was log(n^2), this would be O(log(log^2(n^2))). With it's actual upper bound, the inner loop is O(log(n^2 * n^2)) and as previously shown the whole algorithm is O(log^2(n)).


mojo666: I meant to say that the outer loop's upper bound was O(log(n2)).

Quote

With it's actual upper bound, the inner loop is O(log(n^2 * n^2)) and as previously shown the whole algorithm is O(log^2(n)).


Not quite sure how you arrived at that answer, but I wouldn't doubt it's correct. You seem to know complexity pretty well. I do know that sepp2k's answer is the same as mine though.

This post has been edited by blackcompe: 25 January 2013 - 03:01 PM

Was This Post Helpful? 0
  • +
  • -

#8 antolin  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 2
  • Joined: 25-January 13

Re: big O exponential

Posted 26 January 2013 - 08:12 AM

Hi all, thanks for the fast and detailed response, however I do have some further questions to ask, please be patient on a newbie like me. Really appreciate your guidance on this Big O notation

View Postsepp2k, on 25 January 2013 - 08:33 AM, said:

Quote

so does it mean that O(log n * (n * n * n)) equals to O(log n^4)


No, it doesn't. x log y (or (log y) * (x), which is the same thing of course) is not the same thing as log (x*y). Your code is (log n) * (n * n * n), which can be more succinctly written as n^3 log n. It's not log n^4.


So in the end what is O(n^3 log n) is it O(n log n) but since the power is not a constant it shouldn't be taken off, or does it mean that it is O(n^3) only, since n^3 is bigger than log n. However I think O(n^3 log n) should be itself which is O(n^3 log n) as the end result of the Big O am I right?

View Postsepp2k, on 25 January 2013 - 08:33 AM, said:

Quote

Lastly, If I have a for loop such as the following

for(int i = 0; i < n*n; *= 2) {
	for(int j = 0; j < i*i; *= 3){
		//content running in constant time
	}
}

would it be
first loop: ((log n)*(n*n)) * second loop: ((log n) * (n*n)) equals to O(log n^3)^2 ?


Actually that's an infinite loop because 0*2 is still 0. So I'll assume that i and j actually start at 1 (and that *= 2 and *= 3 actually read i *= 2 and j *= 3 respectively).

If you're iterating from 1 to some value x by doubling the value of x at each iteration, you need log x steps. In your case x is n^2 so the outer loop is log n^2. The inner loop is log i^2, so if we consider that the upper bound for i is n^2 we know that the inner loop is O(log (n^2)^2) = O(log n^4). That would make the whole loop O((log n^2) * (log n^4)). However I'm not sure whether that's also its big-Theta.

So what would be the end Big O notation result for O((log n^2) * (log n^4)? Is it O(log n^8)= O(log n)

Thanks for helping me understanding this Big O notation in detail, I do really appreciate it
Was This Post Helpful? 0
  • +
  • -

#9 blackcompe  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 1155
  • View blog
  • Posts: 2,533
  • Joined: 05-May 05

Re: big O exponential

Posted 26 January 2013 - 11:12 AM

Quote

So in the end what is O(n^3 log n) is it O(n log n) but since the power is not a constant it shouldn't be taken off, or does it mean that it is O(n^3) only, since n^3 is bigger than log n. However I think O(n^3 log n) should be itself which is O(n^3 log n) as the end result of the Big O am I right?


O(n3log(n)) is the end result. You can only get rid of constant coefficients and lower order terms. You want to keep the term that dominates the rest. For instance, if you had O(2n3log(n) + n2), you could drop the 2 and the n2.

Dropping log(n) sounds reasonable, since n3 is much bigger, but if you dropped it, you'd loosen (tighten) the upper bound. O(n3log(n)) is a tighter (looser) (more accurate) upper bound. I think that's correct anyway.

Quote

So what would be the end Big O notation result for O((log n^2) * (log n^4)? Is it O(log n^8)= O(log n)


To correct you, (log(n2) * log(n4)) = 8log2(n). You can drop the coefficient, which leaves you with log2(n).

This post has been edited by blackcompe: 26 January 2013 - 01:11 PM

Was This Post Helpful? 1
  • +
  • -

#10 sepp2k  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 2113
  • View blog
  • Posts: 3,234
  • Joined: 21-June 11

Re: big O exponential

Posted 26 January 2013 - 11:36 AM

View Postblackcompe, on 26 January 2013 - 07:12 PM, said:

Dropping log(n) sounds reasonable, since n3 is much bigger, but if you dropped it, you'd loosen the upper bound. O(n3log(n)) is a tighter (more accurate) upper bound. I think that's correct anyway.


Actually O(n^3) is the tighter upper bound. It's also incorrect in this case.

This post has been edited by sepp2k: 26 January 2013 - 11:37 AM

Was This Post Helpful? 1
  • +
  • -

#11 blackcompe  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 1155
  • View blog
  • Posts: 2,533
  • Joined: 05-May 05

Re: big O exponential

Posted 26 January 2013 - 11:50 AM

Quote

Actually O(n^3) is the tighter upper bound. It's also incorrect in this case.


You're right. I screwed up my words. Corrected. Thanks.
Was This Post Helpful? 0
  • +
  • -

#12 sepp2k  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 2113
  • View blog
  • Posts: 3,234
  • Joined: 21-June 11

Re: big O exponential

Posted 26 January 2013 - 01:07 PM

I don't mean to belabor the point, but when you say O(n log(n)) is more accurate, that still makes it sound as if O(n) would also be technically correct (albeit less accurate). But it's not.
Was This Post Helpful? 1
  • +
  • -

#13 blackcompe  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 1155
  • View blog
  • Posts: 2,533
  • Joined: 05-May 05

Re: big O exponential

Posted 26 January 2013 - 01:12 PM

Quote

I don't mean to belabor the point, but when you say O(n log(n)) is more accurate, that still makes it sound as if O(n) would also be technically correct (albeit less accurate). But it's not.


I agree. Corrected.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1