What would the complexity (Big-O notation) for the following function:
func sortList(_ thresholdValue: Int) -> [Int] {
var currentValue = thresholdValue
//Values is an array of integers - [Int]
var valArr = values.sorted { $0 > $1 } //should be a merge sort O(nlogn)
for i in 0...valArr.count-1 {
if valArr[i] < currentValue {
currentValue = currentValue - valArr[i]
} else {
let tempArr = filter(valArr[0...i-1], currentValue) // O(n) - array splicing
if tempArr.count > 0, let updatedValue = tempArr.first {
currentValue = currentValue - updatedValue
valArr = updateArr(array: valArr, fromIndex: valArr.index(of: updatedValue)!, toIndex: i)
currentValue = thresholdValue
} else {
currentValue = thresholdValue - valArr[i]
}
}
}
return valArr
}
func updateArr<T>(array: Array<T>, fromIndex: Int, toIndex: Int) -> Array<T>{
var arr = array
let element = arr.remove(at: fromIndex) // O(n)
arr.insert(element, at: toIndex) // O(n)
return arr
}
func filter(_ tempArr:ArraySlice<Int>,_ currentValue : Int) -> [Int]{
for value in tempArr { // O(n)
if let index = values.index(of: value) {
tempArr.remove(at: index) // O(n)
}
}
return tempArr.filter { $0 <= currentValue }.sorted { $0 > $1 } //O(n) O(mlogm)
}
The above function tries to rearrange an of integers such that the sequence (not a subarray) of elements sum up to a value less than or equal to k. Once the sequence completes, a new sequence (in the same array) sums to a value less than or equal to k. I have added the possible complexity for each execution possible (not O(1)).
I believe the structure of your code can be viewed more simply like this:
sort values (O(nlogn) operation)
loop over values (O(n) operation)
if some condition is satisfied
perform O(1) operation
else
perform O(n) operation
if some condition is satisfied
perform O(n) operation (updateArr)
else
perform O(1) operation
First you perform a sort, then you loop over your input and perform O(n) operations in that loop based on some conditions. The worst case in this situation is if you perform any number of the O(n) operations inside your loop a number of times related to your input size. Your loop's time complexity in this case would be O(n * (n-m)) where m is a non-constant number related to your input size which is the number of times you do not perform the O(n) operations in your loop. This simplifies to O(n^2 - n*m), which is O(n^2). Your loop's complexity is larger than that of your sort, so your final complexity is O(n^2).