Simple question about data structures.....

Question

1.00/5 (1 vote)

See more:

How to count primitive operations in algorithm? Please, with simple example

Algorithm arrayMax(A, n)
# operations
1.currentMax <- A[0] 2
2. for (i =1; i<n;>
(i=1 once, i<n n="" mode="hold"> 3. if A[i] > currentMax then 2(n - 1)
4. currentMax < A[i] 2(n - 1)
return currentMax 1
Total 6n-1

above is algorithm of finding max number in array i am confusing above primitive operations in line 3 and line 4

how is 2(n-1)?

Posted 19-Jan-12 4:13am

ALIWAZ

Updated 19-Jan-12 4:53am

v4

Add a Solution

Comments

Albert Holguin 19-Jan-12 10:18am

Your question is not clear, use "Improve question" to add details of what you're trying to achieve (and what it has to do with data structures). Also, type full sentences and make them readable please.

Stefan_Lang 19-Jan-12 10:59am

It's ok to write pseudocode, but this (referring to v4) is unreadable. Apart from the for loop there is no recognizable program structure. Please use brackets consistently, use C-like syntax for conditional execution (if (...) {...} else {...}), don't write multiple operations in one line, and don't split a single operation into multiple lines.

Sergey Alexandrovich Kryukov 19-Jan-12 12:54pm

What do you call a "primitive operation"? Why do you want to count them? What's the goal of this?
--SA

Chris Meech 19-Jan-12 15:39pm

Add some <pre> tags around your code. I think it has been messed up with out them.

YvesDaoust 25-Jan-12 11:29am

By the way, your title is misleading.

2 solutions

Add a Solution

Add your solution here

Treat my content as plain text, not as HTML

Preview 0

…

Existing Members

Sign in to your account

...or Join us

Download, Vote, Comment, Publish.

Your Email
Password
Forgot your password?

Your Email
This email is in use. Do you need your password?
Optional Password

I have read and agree to the Terms of Service and Privacy Policy
Please subscribe me to the CodeProject newsletters

When answering a question please:

Read the question carefully.
Understand that English isn't everyone's first language so be lenient of bad spelling and grammar.
If a question is poorly phrased then either ask for clarification, ignore it, or edit the question and fix the problem. Insults are not welcome.
Don't tell someone to read the manual. Chances are they have and don't get it. Provide an answer or move on to the next question.

Let's work to help developers, not make them feel stupid.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

YvesDaoust · Answer 1 · 2012-01-25T05:28:00

It is up to you to define what your primitive operations are, and you should count separately per primitive type.

For instance, you might count the loop iterations (n), the array accesses (n), the comparisons to the maximum (n-1), and/or the value assignments (m, the number of so called "left-to-right maxima", in range [0..n]).

Counts are usually kept separate for clearer accounting and also because you don't want to assign every operation a specific number of processor clocks.

In practice, it is often the case that you focus on only one type of operation that describes the overall behavior of the algorithm. In your example, you would probably consider the number of comparisons to the maximum, all the rest being proportional or less.

This is in relation with the notion of asymptotic complexity http://en.wikipedia.org/wiki/Asymptotic_computational_complexity[^].

YvesDaoust · Answer 2 · 2012-01-25T05:38:00

Solution 2

The only explanation I could imagine to your (dirtily) annotated code is that the comparison and assignment statements have a cost of 2 units. This would explain the 2(n-1) on line 3 (executed exactly n-1 times). And would reveal a mistake on line 4 (executed AT MOST n-1 times).

Posted 25-Jan-12 5:38am

YvesDaoust