How do you go about justifying the correctness and runtime of an algorithm?
For example, say I'm asked to justify the correctness and runtime of an algorithm that is essentially counting sort.. I know it runs in worst case O(n), but idk how to justify the correctness or prove that the runtime is O(n).
Question: Describe an algorithm to sort n integers, each in the range [0..n4 − 1], in O(n) time. Justify the correctness and the running time of your algorithm.
Work:
Algorithm to sort n integers in the range [0..(n^4)-1] in O(n)
Use countSort with respect to the least significant digit
countSort with respect to the next least significant digit
Represent each int x in the list as its 4 digits in base n
let k = (n^4)-1 the max value in the range
Since values range from 0..k, create k+1 buckets
Iterate through the list and increment counter each time a value appears
Fill input list with the data from the buckets where each key is a value in the list
From smallest to largest key, add bucket index to the input array
Variables:
array: list of ints to be sorted
result: output array (indexes from 0..n-1)
n: length of the input
k: value such that all keys are in range 0..k-1
count: array of ints with indexes 0..k-1 (starts with all = 0)
x: single input value
total/oCount: control variables
total=0
for x in array
count[key of x] ++
for i < length of k-1
oCount = count[i]
count[i] = total
total += oCount
for x in array
result[count[key of x]] = x
count[key of x] ++
return result
The algorithm uses simple loops without recursion. Initializing the count array and the middle for loop that calculates sum on the count array iterate at most k+1 times. The 1 is constant so this takes O(k). Looping to initialize the result array and input array will take O(n) time. These total to O(n+k) time. k is considered a constant, so the the final running time is O(n)
I need some help to point me in the correct direction. Thanks!