Programming Forums > Application Development > C

beginnerCCC · Nov 8th, 2006, 9:36 PM

hey guys,

can anyone give me a way to determine the complexity of an algorithm in the big o notation??

i will give an example and please provide me with the way that i should do it, thanks.

(Toggle Plain Text)

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

also this is another example:

(Toggle Plain Text)

for(cnt=0, i=0; j<n; i++)
   for(j=0; j <= i; j++)
         cnt++;

thanks

dark_omen · Nov 8th, 2006, 9:45 PM

I am pretty sure the complexity of the first one is O(log_2(n))
and the second one is O(n^2).

beginnerCCC · Nov 8th, 2006, 10:38 PM

but how can determine it??

dark_omen · Nov 8th, 2006, 11:14 PM

you determine it by how it grows. For instance you have a nested for statements like this:

(Toggle Plain Text)

for(int i = 0; i < n; i++){
     for(int j = 0; j < n; j++){
          //some statements;
     }
}

then it is O(n^2), because each of the for loops is n, so T(n) = n * n = n^2
In your first example you have i *= 2, which is not linear, and when you have something growing like i *= 2 the complexity is log(n).
Simple statements, like int i = a + b, are of complexity 1.
Another example:

(Toggle Plain Text)

for(int i = 0; i < n; i++){//complexity n
     int tm += i;//complexity 1
}

So then the equation for time T(n) = n + 1
and the complexity is the highest power of the equation, in this case n, so complexity is O(n).
Hope this helps, you also may want to google it to get a better description of it.

Iftikhar · Nov 9th, 2006, 6:33 AM

You can have further expanation of determining compexity of algorithums from the following URL http://www.cs.bham.ac.uk/~mhe/foundations2/node121.html

Kaja Fumei · Nov 9th, 2006, 11:04 AM

Actually your first code results in an infinite loop when n > 0. The outer loop mulitplies i by 2 at the end, and since i starts at 0 and 0 * 2 == 0, i will be always be 0.

Nov 8th, 2006, 9:36 PM	#1
beginnerCCC Newbie Join Date: Sep 2006 Posts: 29 Rep Power: 0	algorithm complexity hey guys, can anyone give me a way to determine the complexity of an algorithm in the big o notation?? i will give an example and please provide me with the way that i should do it, thanks. (Toggle Plain Text) for(cnt = 0, i=0; i < n; i = 2 ) for(j=0; j<n; j++ ) cnt++; for(cnt = 0, i=0; i < n; i = 2 ) for(j=0; j<n; j++ ) cnt++; also this is another example: (Toggle Plain Text) for(cnt=0, i=0; j<n; i++) for(j=0; j <= i; j++) cnt++; for(cnt=0, i=0; j<n; i++) for(j=0; j <= i; j++) cnt++; thanks

Nov 8th, 2006, 11:14 PM	#4
dark_omen Hobbyist Programmer Join Date: Dec 2004 Posts: 125 Rep Power: 4	you determine it by how it grows. For instance you have a nested for statements like this: (Toggle Plain Text) for(int i = 0; i < n; i++){ for(int j = 0; j < n; j++){ //some statements; } } for(int i = 0; i < n; i++){ for(int j = 0; j < n; j++){ //some statements; } } then it is O(n^2), because each of the for loops is n, so T(n) = n * n = n^2 In your first example you have i = 2, which is not linear, and when you have something growing like i = 2 the complexity is log(n). Simple statements, like int i = a + b, are of complexity 1. Another example: (Toggle Plain Text) for(int i = 0; i < n; i++){//complexity n int tm += i;//complexity 1 } for(int i = 0; i < n; i++){//complexity n int tm += i;//complexity 1 } So then the equation for time T(n) = n + 1 and the complexity is the highest power of the equation, in this case n, so complexity is O(n). Hope this helps, you also may want to google it to get a better description of it.

Nov 9th, 2006, 6:33 AM	#5
Iftikhar Programmer Join Date: Oct 2006 Location: London Posts: 40 Rep Power: 0	You can have further expanation of determining compexity of algorithums from the following URL http://www.cs.bham.ac.uk/~mhe/foundations2/node121.html __________________ Iftikhar Ahmed Khan For doing an experiment on programmer's mood please visit http://uxisfyp1.brunel.ac.uk/cspgiak

Thread Tools
Show Printable Version Email this Page
Display Modes
Linear Mode Switch to Hybrid Mode Switch to Threaded Mode

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
prim's algorithm	cwl157	C++	7	Apr 18th, 2006 9:45 PM
algorithm of fast exponentiation	MicRo	C++	1	Mar 12th, 2006 6:29 PM
SpcFileWipe algorithm in Secure Programming Cookbook not working	c0ldshadow	C++	1	Aug 7th, 2005 8:40 PM
rsa encrption decrption algorithm	justdoit	C	2	May 4th, 2005 10:16 AM
Help with some algorithm questions	mapster123	Assembly	3	Feb 14th, 2005 5:55 AM

Nov 8th, 2006, 9:45 PM	#2
dark_omen Hobbyist Programmer Join Date: Dec 2004 Posts: 125 Rep Power: 4	I am pretty sure the complexity of the first one is O(log_2(n)) and the second one is O(n^2).

Nov 8th, 2006, 10:38 PM	#3
beginnerCCC Newbie Join Date: Sep 2006 Posts: 29 Rep Power: 0	but how can determine it??

Nov 9th, 2006, 11:04 AM	#6
Kaja Fumei Hobbyist Programmer Join Date: Oct 2005 Posts: 134 Rep Power: 4	Actually your first code results in an infinite loop when n > 0. The outer loop mulitplies i by 2 at the end, and since i starts at 0 and 0 * 2 == 0, i will be always be 0.

Currently Active Users Viewing This Thread: 1 (0 members and 1 guests)

Programming Forums > Application Development > C

algorithm complexity