Determining Big O Notation

An easier way

  • (4 Pages)
  • +
  • 1
  • 2
  • 3
  • 4

53 Replies - 143810 Views - Last Post: 02 March 2013 - 05:43 PM Rate Topic: -----

#16 KYA  Icon User is offline

  • g++ jameson.cpp -o beverage
  • member icon

Reputation: 3106
  • View blog
  • Posts: 19,145
  • Joined: 14-September 07

Re: Determining Big O Notation

Posted 30 March 2010 - 09:00 PM

@quophyie

1. It iterates 12 times so the exactly growth rate is stable, you "could" say O(12) or O(1)

2. yes, log(n) means you need to raise that number to a certain power to get that number. The smallest way to get log(n) is to multiply the increment by 2 (larger numbers also work and probably have a more exact answer, but I lump them into log(n)).

3. That is an infinite loop.

4. No idea. It's a typo, I'll fix it.

5. It's only O(n) if it iterates 'n' number of times, where 'n' is the # of elements in the data structure. Since we're multiplying n by itself we now iterate O(n^2) times.
Was This Post Helpful? 0
  • +
  • -

#17 xTorvos  Icon User is offline

  • D.I.C Regular
  • member icon

Reputation: 61
  • View blog
  • Posts: 271
  • Joined: 23-October 09

Re: Determining Big O Notation

Posted 30 March 2010 - 09:42 PM

View PostKYA, on 12 September 2009 - 04:03 PM, said:

for(int i = 0; i < n; i *= 2) {
	cout << i << endl;
}



for(int i = 0; i < n; i++) { //linear
	for(int j = 0; j < n; j *= 2){ // log (n)
		//do constant time stuff
	}
}



Last time I checked (about 1.5 minutes ago), taking 0 * 2 gives me 0. I'm thinking your Big O is a little more than log(n). ;)
Was This Post Helpful? 0
  • +
  • -

#18 Guest_quophyie*


Reputation:

Re: Determining Big O Notation

Posted 31 March 2010 - 02:55 AM

Cheers KYA!! It all makes sense now especially the log(n) bit. Thanks you very much for making Big-O clear and easy to understand. In all my years at university, non of my lecturers were able adequately to explain big-O and how its applied and its taken your simple blog to explain it. Thanks again man!!!
Was This Post Helpful? 0

#19 KYA  Icon User is offline

  • g++ jameson.cpp -o beverage
  • member icon

Reputation: 3106
  • View blog
  • Posts: 19,145
  • Joined: 14-September 07

Re: Determining Big O Notation

Posted 02 April 2010 - 08:59 PM

View PostxTorvos, on 30 March 2010 - 09:42 PM, said:

Last time I checked (about 1.5 minutes ago), taking 0 * 2 gives me 0. I'm thinking your Big O is a little more than log(n). ;)



Fixed.


@quophyie glad you found it helpful.
Was This Post Helpful? 0
  • +
  • -

#20 Guest_kpb15*


Reputation:

Re: Determining Big O Notation

Posted 06 August 2010 - 02:58 AM

{
  for(j=1; j<=n; j++)
      for(k=1; k<=n; k++)
	 {
	    c[j][k] = 0;
	    for(l=1; l<=n; l++)
		c[j][k] = c[j][k] * b[l][k];
	  }
}


My head hurts. Is this O(n^k)? A simple yes or no would be enough, but I'd really appreciate it if you can point me to the right direction. :death:
Was This Post Helpful? 0

#21 macosxnerd101  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 10647
  • View blog
  • Posts: 39,542
  • Joined: 27-December 08

Re: Determining Big O Notation

Posted 06 August 2010 - 07:06 AM

Technically, it's O(n^3) as you have three nested for loops making n iterations. But it is bounded by O(n^k).
Was This Post Helpful? 0
  • +
  • -

#22 Guest_amit*


Reputation:

Re: Determining Big O Notation

Posted 06 August 2010 - 09:57 PM

Really appreciable and doubt clearing concept u gave.
Was This Post Helpful? 0

#23 ThePheonix21  Icon User is offline

  • D.I.C Head

Reputation: 0
  • View blog
  • Posts: 54
  • Joined: 25-November 09

Re: Determining Big O Notation

Posted 04 September 2010 - 09:22 PM

Just a question, would an if statement nested inside a while loop be considered a nested statement or a sequential statement?
For example:

while(x!=0){
        if(y>z){
           i++;
         }
       }


That's the one thing I noticed wasn't really noted.
Was This Post Helpful? 0
  • +
  • -

#24 macosxnerd101  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 10647
  • View blog
  • Posts: 39,542
  • Joined: 27-December 08

Re: Determining Big O Notation

Posted 05 September 2010 - 08:00 AM

It's additive in regards to efficiency, so it is a constant, and constants are dropped when calculating Big-O.
Was This Post Helpful? 0
  • +
  • -

#25 KYA  Icon User is offline

  • g++ jameson.cpp -o beverage
  • member icon

Reputation: 3106
  • View blog
  • Posts: 19,145
  • Joined: 14-September 07

Re: Determining Big O Notation

Posted 05 September 2010 - 09:37 AM

Alternatively, you could view conditionals constant as well. (Unless said conditional calls a function or such that is known to be a certain runtime, i.e. strlen(), sizeof(), etc...
Was This Post Helpful? 0
  • +
  • -

#26 ThePheonix21  Icon User is offline

  • D.I.C Head

Reputation: 0
  • View blog
  • Posts: 54
  • Joined: 25-November 09

Re: Determining Big O Notation

Posted 05 September 2010 - 11:02 AM

So, a series of If Else statements would be additive as well.

Like:
 if(x==0){
          y++;
       }
       else if(x>0){
          y--;
       }
       else{
         return 0;
       }



View Postmacosxnerd101, on 05 September 2010 - 07:00 AM, said:

It's additive in regards to efficiency, so it is a constant, and constants are dropped when calculating Big-O.

This post has been edited by ThePheonix21: 05 September 2010 - 11:07 AM

Was This Post Helpful? 0
  • +
  • -

#27 macosxnerd101  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 10647
  • View blog
  • Posts: 39,542
  • Joined: 27-December 08

Re: Determining Big O Notation

Posted 06 September 2010 - 06:15 PM

Yes, but for Big-O they are irrelevant as they are constants, and they will get dropped at the end.
Was This Post Helpful? 0
  • +
  • -

#28 Guest_Wilko*


Reputation:

Re: Determining Big O Notation

Posted 09 September 2010 - 08:20 PM

To write O(log(n^3)) would you do say a series of for loops the first being O(logn) then 3 O(n) loops for example

for(int a=1; a<n; a*=2)
		{
			for(int b=1; b<n; b++)
			{
				for(int c=1; c<n; c++)
				{
					for(int d=1; d<n; d++)
					{
					}
				}
			}
		}



And does the form O(k^n) exist? for example O(4^n). because if you multiply nested loops it will give it the other way round like n^4 so not sure how you'd do this.
Was This Post Helpful? 0

#29 Guest_Guest*


Reputation:

Re: Determining Big O Notation

Posted 25 October 2010 - 12:19 AM

View PostWilko, on 09 September 2010 - 07:20 PM, said:

To write O(log(n^3)) would you do say a series of for loops the first being O(logn) then 3 O(n) loops for example

for(int a=1; a<n; a*=2)
		{
			for(int b=1; b<n; b++)
			{
				for(int c=1; c<n; c++)
				{
					for(int d=1; d<n; d++)
					{
					}
				}
			}
		}



And does the form O(k^n) exist? for example O(4^n). because if you multiply nested loops it will give it the other way round like n^4 so not sure how you'd do this.


I am interested in the above mentioned problem as well, anyone knows?
Was This Post Helpful? 0

#30 Guest_Asma Zeb*


Reputation:

Re: Determining Big O Notation

Posted 05 November 2010 - 01:47 AM

sir kindly explain me running time complexity for the following piece of code:

y=0;
x=0;
for (i=n; i>0;i=i-1)
{ y=y+1;}
for (i=1;i<=n;i=i*3)
{ for (j=1;j<=3n;++j)
{
for(k=0;k<n; k=k+5)
{
x=x+5;
}
}
}
Waiting for your positive feed back...i'm getting confused how to find out Big O for nested loops...Thanks
Was This Post Helpful? 0

  • (4 Pages)
  • +
  • 1
  • 2
  • 3
  • 4