| 1234567891011121314151617181920212223242526272829 |
- Stephen Corya
- 00255-99127
- ECE 368
- PA01 Report
- The sequence generation algorihthm generates a sequence based on a max
- value "N". It stores a number of integers equal to the sum of the sequence
- from one to logarithm base-3 of N with increments of one.
- If one imagines the triangle created by 2^p*3^q, it can be thought of as
- the total number of digits in the triangle. Because p+q equals the
- number of operations performed in a given row of the triangle and
- becuase p+q is also to the row number of any given row, the runtime
- complexity of the sequence generation algorithm is equal to O(logsub3
- (N)^2).
- Running the program with an insertion sort on 10.txt gives us 54
- comparisons and 99 moves. The same file sorted with a selection sort gives
- us 151 comparisons and 114 moves. The same program sorting 1000.txt gives
- us 3.071800e+04 comparisons and 5.669300e+04 moves when run using
- insertion sort and 1.199791e+07 comparisons and 7.783800e+04 moves when
- run using selection sort. These values increase exponentially as the size
- of the array to be sorted increases. The runtime complexity of the insertion
- algorithm is approximately equal to O(log(N)*log(N)), as noted in many
- previous studies. The runtime complexity of the selection algorithm
- is significantly greater than its inserting counterpart.
- When run in either insertion or selection mode, the program uses
- approximately one byte of memory per number in the array.
|
