# 13.3 Checkpoint: An Exercise

Exercise: Apply techniques 2A and 2B to `dup2`.

* Calculate the counts of each operation for the following code with respect to N.
* Predict the ***rough*** magnitudes of each one.

```java
for (int i = 0; i < A.length - 1; i += 1){
  if (A[i] == A[i + 1]) { 
    return true; 
  }
}
return false;
```

{% embed url="<https://www.youtube.com/watch?ab_channel=JoshHug&v=IxQh6SXRBRw>" %}

#### Solution:

Note: It's okay if you were slightly off—as mentioned earlier, you want ***rough*** estimates.

| Operation      | Symbolic Count | Count (for N=10000) |
| -------------- | -------------- | ------------------- |
| i = 0          | 1              | 1                   |
| j = i+1        | 0 to $$N$$     | 0 to 10,000         |
| <              | 0 to $$N-1$$   | 0 to 9,999          |
| ==             | 1 to $$N-1$$   | 1 to 9,999          |
| array accesses | 2 to $$2N-2$$  | 2 to 19998          |

{% embed url="<https://www.youtube.com/watch?ab_channel=JoshHug&v=jms0P6p6aQc>" %}
"I have another problem for you to solve ( ͡° ͜ʖ ͡°)..." - Josh Hug
{% endembed %}

Let us compare the `dup1` table with the `dup2` table:

`dup1` table:

| Operation      | Symbolic Count           | Count (for N=10000)                               |
| -------------- | ------------------------ | ------------------------------------------------- |
| i = 0          | 1                        | 1                                                 |
| j = i+1        | 1 to $$N$$               | 1 (in the best case) to 10000 (in the worst case) |
| <              | 2 to $$(N² + 3N + 2)/2$$ | 2 to 50,015,001                                   |
| += 1           | 0 to $$(N² + N)/2$$      | 0 to 50,005,000                                   |
| ==             | 1 to $$(N² - N)/2$$      | 1 to 49,995,000                                   |
| array accesses | 2 to $$N²-N$$            | 2 to 99,990,000                                   |

`dup2` table:

| Operation      | Symbolic Count | Count (for N=10000) |
| -------------- | -------------- | ------------------- |
| i = 0          | 1              | 1                   |
| j = i+1        | 0 to $$N$$     | 0 to 10,000         |
| <              | 0 to $$N-1$$   | 0 to 9,999          |
| ==             | 1 to $$N-1$$   | 1 to 9,999          |
| array accesses | 2 to $$2N-2$$  | 2 to 19998          |

We can see that `dup2` performs significantly better than `dup1` in the worst case!&#x20;

One way to rationalize this is that it takes fewer operations for `dup2` to accomplish the same goal as `dup1`.&#x20;

A better realization is that the algorithm for `dup2` scales much better in the worst case (e.g. ($$N² + 3N + 2)/2$$ vs $$N$$)

An even **better** realization is that parabolas ($$N²$$) always grow faster than lines ($$N$$).