Is variable initialization/assignment statement is a single operation or more?

Question

i'm just learning about algorithm's performance analysis

my question :is int i=0; is counted as two operation: assisgment ,intialization .or it's only one compact operation? i'm using asymptotic analysis which uses the no of operations as a an example of how to describe the performance

this just a way of counting operations and the statement is common between the two languages . i think ! — Karem Emad, Apr 23 '16 at 19:33
For Java (don't know about C++), refer to http://stackoverflow.com/questions/3463658/are-64-bit-assignments-in-java-atomic-on-a-32-bit-machine — Tunaki, Apr 23 '16 at 19:34
@KaremEmad - this statement inside a class for an instance member variable 'i' could mean different things in C++ and Java. In C++ this will be initialized with the value provided but in Java i guess there is a default value initialization followed by assignment with the value specified. — MS Srikkanth, Apr 23 '16 at 19:35
If you want a Java-specific answer, why did you tag this with C++11? — Some programmer dude, Apr 23 '16 at 19:35
but i want to know what will be the answer in the two (java-c++) — Karem Emad, Apr 23 '16 at 19:36
the question which you provide is not similar to mine or i couldn't understand, Tunaki — Karem Emad, Apr 23 '16 at 19:37
@KaremEmad - Tunaki's point is that a write to 64 bit values in java can be 2 32-bit word writes instead of one atomic write. So in your case it will be counted as 2 operations instead of one — MS Srikkanth, Apr 23 '16 at 19:39
For the purposes of asymptotic analysis - your purported goal - the answer to your question would not matter in the slightest. All that matters is that the time to execute this construct has some constant upper bound. — Igor Tandetnik, Apr 24 '16 at 00:57

score 0 · Answer 1 · answered Apr 24 '16 at 00:57

There is not one correct answer to this.

In some contexts, people may analyze a single arithmetic operation as being "one" operation. Other times, they may care a lot exactly how many cycles an operation will take, and they may want to say that e.g. adding ints is cheaper than multiplying floats.

In many contexts, programmers say that dereferencing a pointer is O(1). However, if you really are considering the case when n goes to infinity, if your n is like the size of the universe, does it still make sense to say that dereferencing a pointer into that is O(1) operation? In some theoretical contexts, people will say that dereferencing a pointer is O(log n) essentially.

However, I talked to a physicist once who said that even O(log n) possibly is not physically realistic -- he says there is a maximum information density that the universe can have in a given volume space. This is called the "Bekenstein Bound", it turns out that the maximum entropy is achieved by a black hole. If you assume that in a volume of space n you can only have O(n) bits of memory, it basically means that in a galactic-sized computer, bits have to be packed like balls in the sphere packing problem, and then the distance between a typical pair of bits is growing as O(n^{1/3}). Since information doesn't go faster than speed of light... maybe dereferencing a pointer needs O(n^{1/3}) asymptotically? O.o

Point is, don't overthink this. Any thing that you do in asymptotic analysis is ultimately an approximation, you are just trying to get a useful idea of how long it will take. Things that you are pretty sure won't really matter in your case, you can analyze as O(1), in order to focus on the things that do matter. In another situation, those same things you may want to analyze differently, if they represent "most" of the work.

IMO if you want to know how to answer questions about this stuff in a job interview, you should be prepared to analyze it in multiple different ways, and show them that you understand that things like "does int i = 0; count as one operation or two" are basically a convention.

Is variable initialization/assignment statement is a single operation or more?

1 Answers1