visitor (0 QPoints)
  • FR
  • EN
  • NL
  • DE
  • ES
315 experts, 1193 registered users, 1659 questions already answered
European Experts Exchange, the very best site for high-quality IT solutions

New Improved Search!

 


05/10/2011 1h30 : Steve Jobs is dead, the father of Apple ][ is gone, we are all orphaned.

Algorithms :: Maths :: asymptotic complexity
By: tppradeep18 U.S.A.  Date: 03/08/2003 00:00:00  English  Points: 100 Status: Answered
Quality : Excellent
I am new to the subject of asymptotic complexity. I need to find out the asymptotic complexity of the following in the context of Big ‘Oh’ ( ¼ ), Omega ( ¿ ) and Theta ( è ) .

Algorithm Sum (a,n)
{
S := 0.0 ;
For i := 1 to n do
S := s + a ;
return S ;
}

Though I understand the asymptotic complexity in theory I am really weak in applying it practically. I request someone out there to please help me out with the above sample. I would be grateful if some explanation is give as to how to find the asymptotic complexity.
By: VGR Date: 03/08/2003 17:36:00 English  Type : Comment
well, first of all, complexity is "in something" : it an be a complexity in time, in operations, in affectations, in additions, in tests & comparisons, etc

In your case, I guess it's in additions (monotonic : all are supposed to take the same number of clocks/cycles), which execution time is t

Then your algorithm above is clearly :
execute n times
add s with a

so, "in additions", your algorithm is "in O(n)"

it's asymptotic compleciry is also in O(n) as there are no constants or lesser-order terms to ignore when tending towards infinite
By: VGR Date: 03/08/2003 17:38:00 English  Type : Answer
an arbitrary example to demonstrate asymptotic complexity :

let's imagine an algorithm is "in O(3n²+254n+12)" : then it's asymptotic complexity is "in O(n²)" as all other terms become negligible when n tends towards (plus) infinite

that's simple in fact

hope this helps
By: GwynforWeb Date: 03/08/2003 18:16:00 English  Type : Comment
tppradeep18,
The example you have been given is not a good one in that it does not really allow the difference between the three quantities Big ‘Oh’ ( ¼ ), Omega ( ¿ ) and Theta ( è ) to be illustrated , for this alogorithm they are all the same ie O(n), Omega(n) and Theta(n)., ie upper bouind on worse case, lower bound on best case, theta being a combination respectively and is a little trickier.

People get into a muddle with complexity analysis when it is much more simple than they think. Bubble sort is a better example it is O(n²) & Omega(n), ie it can do it in n operations if already sorted and it can be as bad as n² if in reverse order. When calculating these quantities you must pay attention to worst case and best case scenarios both as functions as n and then form asymptotic bounds on those functions. For the example you havegiven clearly these are same.

(Here is an interesting trivia point techniqually quicksort is O(n²) and Omega(nln n). however its average behaviour is Theta(nln n ))

GfW
By: GwynforWeb Date: 03/08/2003 18:19:00 English  Type : Comment
ps bubble sort is theta(n²)
By: grg99 Date: 03/08/2003 18:35:00 English  Type : Comment
"(Here is an interesting trivia point techniqually quicksort is O(n²) and Omega(nln n). however its average behaviour is Theta(nln n ))"

Yes, but it's easy to add just a few lines to improve quicksort
to detect when it's going to be slow, and thereby switch to a faster search scheme.

With bubble sort, you're stuck with O( n squared )
By: GwynforWeb Date: 03/08/2003 19:09:00 English  Type : Comment
grg99,

" Yes, but it's easy to add just a few lines to improve quicksort
to detect when it's going to be slow, and thereby switch to a faster search scheme."

it does not matter how you try to improve quick sort it is still O(n²), ie the upper bound on its asymptotic behaviour is O(n²) but it so rarely gets near this upper bound and for the most part it's behaviour is closer to the asymptotic lower bound Omega(nln n), it is almost always is better than say merge sort which is O(nln n). This is the rare example that confuses the rule of thumb that O(n²) is faster than O(nln n ).

The lower bound on bubble sort is Omega(n) which can occur for already sorted data, the average behaviour (ie theta) is still however very firmly stuck in the n² range and as such is pathetically slow.
By: tppradeep18 Date: 05/08/2003 00:27:00 English  Type : Comment
hi VGR ,

Your suggestion are good. But could u please tell me what should have been the statement in the loop for
O(n2),O(n3),O(n4)". I little understand what exactly is CONSTANT doing here. If my statement was 17n3+n would the constant be 17 here. If so what would be the asymptotic complexity.

thanks
By: tppradeep18 Date: 05/08/2003 00:29:00 English  Type : Comment
please read n3 as n raise to the power 3 etc.
By: GwynforWeb Date: 05/08/2003 01:22:00 English  Type : Assist
tppradeep18: To fully understand the the mathamatical defintion of big 'O' for a function I strongly recommend you look at and master the technical definition.

In short it means that a function f(n) is big 'O' some other function G(n) if for n large enough then there is some constant K st

f(n) < KG(n)

eg for f(n)=3n²+21n
=3(n²+7n)

for n > 7 then 7n<n²

so 3(n²+7n) < 3(n²+n²) =6n²

This now gives that

f(n)=3n²+21n < 6n² if n > 7

ie f(n) is bounded above by some quadratic for sufficiently large n, so we say

f(n) = O(n²)


Hope that helps

GfW
By: VGR Date: 05/08/2003 02:15:00 English  Type : Comment
O(z) ("big o", not "small o") is exactly what Gwynforweb posted. It means that there exists a constant k so that when n tends towards infinite, f(n)<k.z

isn't this the order of magnitude ?

And in my first explanation, "constants" are order magnitude zero so they are part of the "lesser order terms" I mentioned as negligible when n tends towards infinite.

In fact , taking Gwyn's example, I would have written :

f(n)=3n²+21n = (3+21/n).n² -> 3.n² when n->infinite as 21/n -> zero
and obtained the order of magnitude this way
By: GwynforWeb Date: 06/08/2003 00:14:00 English  Type : Comment
When first learning this subject I recommend the method I have shown it is a formal and rigorous method. However when you get good at it you will be abled to tell by looking at a function what its properties are eg

4n³-2n²+n+18 is O(n³) and Gamma(n³)

7n²-2n+3 is O(n²) and Gamma(n²)

-2n+3n²sin(n) is O(n²) and Gamma(n)

(the formal technique also allows you to analize functions that are not so simple and you should master it)

GfW
By: GwynforWeb Date: 06/08/2003 00:27:00 English  Type : Comment
Sorry I meant to add that when you are more skilled at this the method VGR mentioned may be one you could use and there are others. But when I first learnt this I was made to do endless examples of the nature I showed. I rarely use that now however I need it when I come across a function that is more complex and unfamiliar to me. GfW
By: VGR Date: 06/08/2003 04:13:00 English  Type : Comment
well, I consider wjat you call "my" method as just "the mathematical one" ; at least that's the one I learnt.
By: GwynforWeb Date: 06/08/2003 04:49:00 English  Type : Comment
VGR, I am was not trying to be rude. I am only reproducing what you would find in a good mathematical computer science book and what would be expected of you in a unversity course in computer science. The method you have described does not formally demonstrate that for sufficiently large and finite n that there exists K st f(n) < K×G(n) which is the rigorous definition of Big O.
By: SethHoyt Date: 22/08/2003 07:14:00 English  Type : Comment
Gwyn is correct here.

There is good reason for the asymptotic notations to be defined the way they are. It has to do with the fact that you don't need to know the actual running time to know the asymptotic complexity. In fact, the actual running time may not even be knowable.

For example, if you have a machine that takes variable amounts of time to complete a given operation (perhaps depending on core temperature), as long as you can put an upper bound on the time, it is O(1). It's incorrect to refer to O(1) as constant because it need not be; "bounded above" is a more correct terminology. Any algorithm utilizing such operations would have running times that potentially vary each time, and may have irregular shapes. Only by using the theorems pertaining to the asymptotic complexity classes can we prove what class it belongs to.

Maybe that example seems contrived, but it's not so far from the truth. In reality, instruction times will vary from machine to machine, and not necessarily proportionally. Thus, using complexity classes is the only feasible way to describe an algorithm's efficiency, not by it's true running time.

-Seth

Do register to be able to answer

©2010 These pages are served without commercial sponsorship. (No popup ads, etc...). Bandwidth abuse increases hosting cost forcing sponsorship or shutdown. This server aggressively defends against automated copying for any reason including offline viewing, duplication, etc... Please respect this requirement and DO NOT RIP THIS SITE.
Please DO link to this page! Post to Twitter Post to Plurk Post to Yahoo Buzz Post to Delicious Post to Digg Post to Facebook Post to MySpace Post to Ping.fm Post to Reddit Post to StumbleUpon

EContact
browser fav
page generated in 365.567920 milliseconds

Why Google AdSense ads ?
compteur
 Ranking-Hits PageRank for this page