Add complexity annotations for functions

I would like to have something like:

@complexity(.time, .O(array.count * .log(array.count)))
sort(array: Array<Element>) {  
  // sort array...
}

It would be nice also to compute complexity of functions:

let arrayOfArrays: [[Int]] = ...

// computed complexity: O(n * n log n) 
func sortSubarrays(array: [[Int]]) {
   // also we know complexity of foreach ( O(n) )
  array.forEach(sort(array:)) // we know complexity of sort(array:)
}

What's different than documenting the complexity today? :thinking: What does this actually solve?

2 Likes

There has been research done on this topic. See the answers on this SO question: https://cs.stackexchange.com/questions/33854/is-there-a-method-for-automatic-runtime-analysis-of-algorithms

It isn’t possible for all algorithms, due to the halting problem. Maybe there are some cases where it can be done, but I’m not sure if it’s worth investing time in to it.

2 Likes