Finding È for an algorithm
I have the below pseudocode that takes a given unsorted array of length
size and finds the range by finding the max and min values in the array.
I'm just learning about the various time efficiency methods, but I think
the below code is È(n), as a longer array adds a fixed number of actions
(3).
For example, ignoring the actual assignments to max and min (as the
unsorted array is arbitrary and these assignments are unknown in advance),
an array of length 2 would only require 5 actions total (including the
final range calculation). An array of length 4 only uses 9 actions total,
again adding the final range calculation. An array of length 12 uses 25
actions.
This all points me to È(n), as it is a linear relationship. Is this correct?
Pseudocode:
// Traverse each element of the array, storing the max and min values
// Assuming int size exists that is size of array a[]
// Assuming array is a[]
min = a[0];
max = a[0];
for(i = 0; i < size; i++) {
if(min > a[i]) { // If current min is greater than val,
min = a[i]; // replace min with val
}
if(max < a[i]) { // If current max is smaller than val,
max = a[i]; // replace max with val
}
}
range = max – min; // range is largest value minus smallest
No comments:
Post a Comment