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: Is there a method for automatic runtime analysis of algorithms? - Computer Science Stack Exchange

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