53 Replies  182243 Views  Last Post: 02 March 2013  05:43 PM
#16
Re: Determining Big O Notation
Posted 30 March 2010  09:00 PM
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.
#17
Re: Determining Big O Notation
Posted 30 March 2010  09:42 PM
KYA, 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).
#18 Guest_quophyie*
Re: Determining Big O Notation
Posted 31 March 2010  02:55 AM
#19
Re: Determining Big O Notation
Posted 02 April 2010  08:59 PM
#20 Guest_kpb15*
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.
#21
Re: Determining Big O Notation
Posted 06 August 2010  07:06 AM
#22 Guest_amit*
Re: Determining Big O Notation
Posted 06 August 2010  09:57 PM
#23
Re: Determining Big O Notation
Posted 04 September 2010  09:22 PM
For example:
while(x!=0){ if(y>z){ i++; } }
That's the one thing I noticed wasn't really noted.
#24
Re: Determining Big O Notation
Posted 05 September 2010  08:00 AM
#25
Re: Determining Big O Notation
Posted 05 September 2010  09:37 AM
#26
Re: Determining Big O Notation
Posted 05 September 2010  11:02 AM
Like:
if(x==0){ y++; } else if(x>0){ y; } else{ return 0; }
macosxnerd101, on 05 September 2010  07:00 AM, said:
This post has been edited by ThePheonix21: 05 September 2010  11:07 AM
#27
Re: Determining Big O Notation
Posted 06 September 2010  06:15 PM
#28 Guest_Wilko*
Re: Determining Big O Notation
Posted 09 September 2010  08:20 PM
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.
#29 Guest_Guest*
Re: Determining Big O Notation
Posted 25 October 2010  12:19 AM
Wilko, on 09 September 2010  07:20 PM, said:
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?
#30 Guest_Asma Zeb*
Re: Determining Big O Notation
Posted 05 November 2010  01:47 AM
y=0;
x=0;
for (i=n; i>0;i=i1)
{ 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
