Algorithm Complexity

[Dan Neely]

Relative weights would vary by CPU architecture. Depending on your data set size and linearity cache sizes would also come into play. Your best bet is the compare actual runtimes, iterating enough that timer noise isn't an issue.

TimerA.Start()
for (int i = 0; i < bigNum; i++)
DoAlgorithmA()
TimerA.Stop()
TimerB.Start()
for (int i = 0; i < bigNum; i++)
DoAlgorithmB()
TimerB.Stop()

if (TimerA.Time > TimerB.Time)
Print ("A is slower");
else
Print ("B is slower");

-- If you view money as inherently evil, I view it as my duty to assist in making you more virtuous.

[Bassam Abdul Baki]

I'm not looking for code complexity, just algorithm. :sigh:

---

"This perpetual motion machine she made is a joke. It just keeps going faster and faster. Lisa, get in here! In this house, we obey the laws of thermodynamics!" - Homer Simpson Web - Blog - RSS - Math - LinkedIn - BM

[Bassam Abdul Baki]

Unfortunately, this is all proof of concept. We wish to estimate which would be better to submit with a proposal.

---

"I know which side I want to win regardless of how many wrongs they have to commit to achieve it." - Stan Shannon Web - Blog - RSS - Math - LinkedIn - BM

[El Corazon]

Bassam Abdul-Baki wrote:

Is anyone aware of such a method?

I generally use a profiler. if you really want a number, test it. Call 1 MILLION calls of a given operation, time it, come up wth a numerical scale for each operand based on the time it takes to call each operation. Now you have a good number.

_________________________ Asu no koto o ieba, tenjo de nezumi ga warau. Talk about things of tomorrow and the mice in the ceiling laugh. (Japanese Proverb)

[Maximilien]

You need to compute the number of operations that each algorithm is doing depending on the size of the inputs. (edit) usually, all binary operations are constant in time. for example : 1+1 is O(1) loops are linear in complexity : j = 0; for ( i = 0; i < n; i++ ) { j++;} is O(n) and so on and so forth.

---

Maximilien Lincourt Your Head A Splode - Strong Bad

[Rama Krishna Vavilala]

Are there any decisons or loops or just formulas?

Co-Author ASP.NET AJAX in Action

[NormDroid]

Interesting, if you do find an article for sheet with the 'weights' of each operator/function I'd be interested to know. Surely someone, somewhere must of done this kind of thing.

WPF - Imagineers Wanted Follow your nose using DoubleAnimationUsingPath

[Ennis Ray Lynch Jr]

If you want to know the number of cycles you could check the chip documentation to determine how many micro cycles a given op will use. With the relatively simple complexity of those algorithms I doubt even big analysis will help. I believe all of those functions use look up tables and identities.

---

Need a C# Consultant? I'm available.
Happiness in intelligent people is the rarest thing I know. -- Ernest Hemingway

[Bassam Abdul Baki]

Just formulas.

---

"There are II kinds of people in the world, those who understand binary and those who understand Roman numerals." - Bassam Abdul-Baki Web - Blog - RSS - Math - LinkedIn - BM

[Bassam Abdul Baki]

I was hoping so. And like I told Rama, it's just for formulas.

---

"Patriotism is your conviction that this country is superior to all other countries because you were born in it." - George Bernard Shaw Web - Blog - RSS - Math - LinkedIn - BM

[Bassam Abdul Baki]

That was my initial suggestion, but they wanted something algebraic and not computed. Go figure.

---

"Dissent is the highest form of patriotism." - Thomas Jefferson Web - Blog - RSS - Math - LinkedIn - BM

[Bassam Abdul Baki]

Unfortunately, they wanted something quick and dirty since this was added to the proposal at the last minute.

---

"Patriotism is your conviction that this country is superior to all other countries because you were born in it." - George Bernard Shaw Web - Blog - RSS - Math - LinkedIn - BM

[Bassam Abdul Baki]

No loops, just equations, with a couple of sin/cos/tan and sqrts.

---

"Marge, don't discourage the boy! Weasling out of things is important to learn. It's what separates us from the animals! Except the weasel." - Homer Simpson Web - Blog - RSS - Math - LinkedIn - BM

[Rama Krishna Vavilala]

Can you give an example or two?

Co-Author ASP.NET AJAX in Action

[El Corazon]

Bassam Abdul-Baki wrote:

but they wanted something algebraic and not computed.

you compute an algebraic weight to be attached to any given function based on its performance time. :)

_________________________ Asu no koto o ieba, tenjo de nezumi ga warau. Talk about things of tomorrow and the mice in the ceiling laugh. (Japanese Proverb)

[Bassam Abdul Baki]

Nope, it's for a proposal. However, I'm talking about any mathematical equation: (a + b) * sin ( π α ) / sqrt(c) ...

---

"There are II kinds of people in the world, those who understand binary and those who understand Roman numerals." - Bassam Abdul-Baki Web - Blog - RSS - Math - LinkedIn - BM

[Bassam Abdul Baki]

True, but they wanted something generic. And like I told others, this was added at the last minute of a proposal and they need it yesterday as usual.

---

"It is the mark of an educated mind to be able to entertain a thought without accepting it." - Aristotle Web - Blog - RSS - Math - LinkedIn - BM

[Shog9 0]

If all you want is a quick "cocktail napkin" comparison, then just count operations by hand, using some large, consistent weight (say, 100) for the trig methods. If the results are close, then you can decide on other factors (clarity, accuracy, ease of optimization, etc.)

every night, i kneel at the foot of my bed and thank the Great Overseeing Politicians for protecting my freedoms by reducing their number, as if they were deer in a state park. -- Chris Losinger, Online Poker Players?

[Marc Clifton]

I haven't read through all the responses you got, but there was a fellow a week ago or so here that posted some results of a genetic algorithm being used to create numeric algorithms. It was very interesting. Marc

Thyme In The Country
Interacx
My Blog

[El Corazon]

time each function individually, assign the fastest operation as "1", assign a number to each other operation based on the timing difference between the shortest operation and it. :) + might be 1 - might be 1 * might be 2.5 / might be 5 sin() might be 10 cos() might be 10 sqrt() might be 20 base each number based on calculated differences, you still have a relative complexity based on CPU time. :) of course ignoring cache flushes, but that is a bit more difficult to catch. :)

_________________________ Asu no koto o ieba, tenjo de nezumi ga warau. Talk about things of tomorrow and the mice in the ceiling laugh. (Japanese Proverb)