i am new to analysis of algorithm . i am having an if condition.

If (I !=j AND A[i]==A[j])

i am counting the operations as

i) accessing element from Array A[] 
ii)compairing i!=j 

iii) compairing a[i]==a[j]

according to me this statement is performing 3 Actions. is it so ? if not than please clarify... thanks


Counting "actions" in this way is completely arbitrary. In order to accurately count basic actions, you need to first come up with a list of basic actions, and then to compile your statement to a list of basic actions. This is exactly what compilers do – they compile your problem to assembly language or, in some cases, to bytecode.

Since you are not specifying your assembly language, it is truly impossible to say anything. It could be that there is one instruction that is equivalent to your if, or it could be that your assembly language is very weak, and your if requires 100 instructions. Even if you did specify your assembly language, it is still not clear how to compile the statement to assembly, since in general there is no canonical way to do so.

The way out is to realize that (under certain conditions) whatever assembly language is used, the statement would compile to a constant number of instructions, whose exact number depends on the assembly language. Therefore we can say that the number of instructions is $O(1)$, where the hidden constant depends on the assembly language and the compiler. In contrast, a loop summing an array would execute $\Theta(n)$ instructions. The difference between $O(1)$ and $\Theta(n)$ exists irrespective of the assembly language and compiler used.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.