Evaluation written in arithmetic operation

38 Views Asked by At

Sorry for my bad English.

I often see the following sentence

in polynomial time $O(n^2)$ arithmetic operation in $\mathbb{Z}$

or

in polynomial time $O(n^2)$ arithmetic operation in $\mathbb{F}_q$

Is my interpretation "arithmetic operation in $\mathbb{F}_q$" is correct?

i.e. for example a calculation $(5+3)\times (3-1)$ is $(5+3)\times (3-1)=8\times (3-1)=8\times 2=16$, so we have 3 arithmetic operation in $\mathbb{Z}$.

If the above interpretation is true, then can we count "addition" and "multiplication"? I think there is big different at the point of time between "addition" and "multiplication".

Please help me.

1

There are 1 best solutions below

0
On BEST ANSWER

Depends on the Context. The writer has to specify which operations are "costly" & which are "easy" , then the given algorithm can be analysed to estimate the number of the costly operations & then claim $O(n^2)$ Etc.

There are Cases when "Comparison" is the Core Operation (eg Sorting) & those algorithms count that Operation to state that Eg Bubble Sort is $O(n^2)$ or other sorting algorithm is $O(n\log{n})$ Etc. Such algorithms may have Multiplication & Addition involved , which are more costly yet do not much contribute to the total running time.

There are algorithms where "Comparison" is immaterial with Multiplication & Addition being the Concern. Eg Matrix Addition or Matrix Multiplication.
In that Case , the writer will specify that Multiplication & Addition are equally costly to then count them both.
Alternately , the writer will specify that Multiplication is very costly (we can ignore Addition) & thus count Multiplications.

Hence Depending on context , your Example has : either 3 Operations (1 Multiplication + 2 Additions) or 1 Operation (1 Multiplication) or 2 Operations (1 Multiplication + 1 Addition , ignoring the "Decrement Operation")

In Some cases , these are floating Point Numbers & all Calculations are somewhat "Equally Costly" , including "Comparison" , "Multiplication" , "Addition" , "Increment Operation" , "Decrement Operation" , "Power functions" , "trig functions" , "log functions" , Etc. Then we count all such Operations towards the total.