Return to Answer

• Because of the 2 imbricated for loops in the original code,

  for (int intI = 0; intI < d; intI++) {
  for (int intK = 0; intK < a.Length; intK++) { ... } }

your code performs d * a.Length actions. Which takes quadratic time when d is near a.Length/2.

So, we may ask, can we do better ?

• The answer is yes. There is a linear-time solution. It is as follows :

1. "mirror" the first d elements
2. mirror the whole array
3. mirror the size-d first elements.

Implementation of mirror (rever an array) is left to the reader.

Linear time complexity. 0(1) extra room needed (loop variable and temporary for exchange).

So it is clearly an improvement on the original version.

Because of the 2 imbricated for loops here:

 for (int intI = 0; intI < d; intI++) {   
   for (int intK = 0; intK < a.Length; intK++) {
               ...
   }
 }

your code performs d * a.Length actions - which takes quadratic time when d is near a.Length/2.

So, we may ask, can we do better ?

The answer is yes. There is a linear-time solution. It is as follows:

1. "mirror" the first d elements
2. mirror the whole array
3. mirror the size-d first elements.

Implementation of mirror (reverse an array) is left to the reader.

Linear time complexity. 0(1) extra room needed (loop variable and temporary for exchange).

So it is clearly an improvement on the original version.

• Because of the 2 imbricated for loops,

  for (int intI = 0; intI < d; intI++) {
  for (int intK = 0; intK < a.Length; intK++) { ... } } your code performs d * a.Length actions. Which takes quadratic time when d is near a.Length/2.

• There is a linear-time solution:

1. "mirror" the first d elements
2. mirror the whole array
3. mirror the size-d first elements.

Implementation of mirror left to the reader.

Linear time complexity. 0(1) extra room needed (loop variable and temporary for exchange).

• Because of the 2 imbricated for loops in the original code,

  for (int intI = 0; intI < d; intI++) {
  for (int intK = 0; intK < a.Length; intK++) { ... } }

your code performs d * a.Length actions. Which takes quadratic time when d is near a.Length/2.

So, we may ask, can we do better ?

• The answer is yes. There is a linear-time solution. It is as follows :

1. "mirror" the first d elements
2. mirror the whole array
3. mirror the size-d first elements.

Implementation of mirror (rever an array) is left to the reader.

Linear time complexity. 0(1) extra room needed (loop variable and temporary for exchange).

So it is clearly an improvement on the original version.

Because of the 2 imbricated for loops,

for (int intI = 0; intI < d; intI++) {   
        for (int intK = 0; intK < a.Length; intK++) {
               ...
        }
}

your code performs d * a.Length actions. Which takes quadratic time when d is near a.Length/2.

There is a linear-time solution:

1. "mirror" the first d elements
2. mirror the whole array
3. mirror the size-d first elements.

In place. Linear time complexity. 0(1) extra room needed (loop variable and temporary for exchange).

• Because of the 2 imbricated for loops,

  for (int intI = 0; intI < d; intI++) {
  for (int intK = 0; intK < a.Length; intK++) { ... } } your code performs d * a.Length actions. Which takes quadratic time when d is near a.Length/2.

• There is a linear-time solution:

1. "mirror" the first d elements
2. mirror the whole array
3. mirror the size-d first elements.

Implementation of mirror left to the reader. 

Linear time complexity. 0(1) extra room needed (loop variable and temporary for exchange).