Calculations prior to determining algorithm complexity order

[s3a]

Hello to everyone who's reading this.

The problem that I'm struggling with, and it's solution, are typed below.:

Homework Statement

PROBLEM STATEMENT:
Assume an array [0, ... n - 1] of int, and assume the following code segment:

for (int i = 0; i < n - 1; i++)
    if(a[i] > a[i+1])
        System.out.println(i);

What is worstTime(n)?

Homework Equations

* Addition and multiplication
* O(n) means |f(n)| <= C*g(n) for all n >= n_0, where n_0 is a placeholder for an integer, and n is a variable that can hold a positive integer. (Generally, I believe the input can be a non-integer real number, but not in the context of the problem that this thread is about.)

The Attempt at a Solution

OFFICIAL SOLUTION:
-----------------------------------------------------------------------------------------
| Statement | Worst case Number of Executions |
-----------------------------------------------------------------------------------------
| i = 0 | 1 |
-----------------------------------------------------------------------------------------
| i < n - 1 | n |
-----------------------------------------------------------------------------------------
| i++ | n - 1 |
-----------------------------------------------------------------------------------------
| a > a[i+1] | n - 1 |
-----------------------------------------------------------------------------------------
| System.out.println() | n - 1 |
-----------------------------------------------------------------------------------------

MY CONFUSION(S):
What I am confused about is (at least) the following two things.:
1:
Why is each time i < n - 1 is run, considered to be one instruction (to be executed), instead of two? Isn't it the case that the subtraction operator and the less-than operator are each considered to be one instruction (to be executed), such that the the total number of instructions (to be executed) of i < n - 1 should be 2*n, instead of n? I have a similar confusion with a > a[i+1] being counted as one instruction (to be executed), rather than 2, such that the total instruction (to be executed) of a > a[i+1] seems to me that it should be 2*(n-1), rather than n - 1.

I get that, even if the solution was changed to what I'm saying above, the order of the worst-case running time would remain the same, as O(n), but could someone still please tell me if it's a mistake in the solution, or if it's not a mistake, could I please have the flaw in my logic pointed out?

2:
Do all instructions (to be) executed) have the same weight? In other words, is each instruction (to be executed) equally demanding for the processor to process (assuming that there is no shortage of any resources)? If not, then why do we treat them all equivalently, as having a weight of 1?

Any input would be GREATLY appreciated!

 

[fresh_42]

Hello to everyone who's reading this.

The problem that I'm struggling with, and it's solution, are typed below.:

Homework Statement

PROBLEM STATEMENT:
Assume an array [0, ... n - 1] of int, and assume the following code segment:

for (int i = 0; i < n - 1; i++)
    if(a[i] > a[i+1])
        System.out.println(i);

What is worstTime(n)?

Homework Equations

* Addition and multiplication
* O(n) means |f(n)| <= C*g(n) for all n >= n_0, where n_0 is a placeholder for an integer, and n is a variable that can hold a positive integer. (Generally, I believe the input can be a non-integer real number, but not in the context of the problem that this thread is about.)

The Attempt at a Solution

OFFICIAL SOLUTION:
-----------------------------------------------------------------------------------------
| Statement | Worst case Number of Executions |
-----------------------------------------------------------------------------------------
| i = 0 | 1 |
-----------------------------------------------------------------------------------------
| i < n - 1 | n |
-----------------------------------------------------------------------------------------
| i++ | n - 1 |
-----------------------------------------------------------------------------------------
| a > a[i+1] | n - 1 |
-----------------------------------------------------------------------------------------
| System.out.println() | n - 1 |
-----------------------------------------------------------------------------------------

MY CONFUSION(S):
What I am confused about is (at least) the following two things.:
1:
Why is each time i < n - 1 is run, considered to be one instruction (to be executed), instead of two? Isn't it the case that the subtraction operator and the less-than operator are each considered to be one instruction (to be executed), such that the the total number of instructions (to be executed) of i < n - 1 should be 2*n, instead of n? I have a similar confusion with a > a[i+1] being counted as one instruction (to be executed), rather than 2, such that the total instruction (to be executed) of a > a[i+1] seems to me that it should be 2*(n-1), rather than n - 1.

I assume the length of the array is a given parameter, as I don't see where it is computed.
Worst case, you are right. The way it is written, it looks like 2 operations per increment. On the other hand, an additional line int k=n-1 with iteration i < k would give only 1 additional step and n+1 in total, or n if the last index of a is already given. Furthermore all depends on which model you use. If the compiler sets up the loop only once, then the loop boundary n-1 is computed only once, too.

I get that, even if the solution was changed to what I'm saying above, the order of the worst-case running time would remain the same, as O(n), but could someone still please tell me if it's a mistake in the solution, or if it's not a mistake, could I please have the flaw in my logic pointed out?

2:
Do all instructions (to be) executed) have the same weight? In other words, is each instruction (to be executed) equally demanding for the processor to process (assuming that there is no shortage of any resources)? If not, then why do we treat them all equivalently, as having a weight of 1?

This depends on the underlying model as well. Since we count time, it is normal to count each single step. However, there are other models, which distinguish, e.g. addition and multiplication. A famous example is the matrix exponent $\omega = \inf \,\{r \in \mathbb{R}\,\vert \, \text{ there exists an algorithm for matrix multiplication which stops in } O(n^r) \} \,.$
To treat them as all having weight one is certainly a simplification. It probably comes from the model of a TM which stops after a certain number of steps, each step representing a calculation. In real world problems it can be necessary to be more precise. But on the one hand, the weights will largely depend on the given environment, e.g. the machine used, and on the other hand it turns out, that the most time consumption steps are always I/O, whether from a file or a database access. The actual computations are meanwhile so fast, that they often can be neglected in comparison with I/O. However, not always. And in these examples it might well be necessary to distinguish different types of steps. In addition you will always have to find a balance between space and time, as you won't always have enough space.