I'm trying to estimate Big-O time and space complexity for the following solutions for a trivial Two Sum Problem. In my understanding, tailrec recursion should be a better solution, but when I try to determine the complexity, it looks like both of them have O(n) for time and O(n) for space.

inputArray = Array(4, 6, 5)
sumToCheck = 9

import scala.annotation.tailrec
import scala.collection.mutable.ListBuffer

def checkTwoSum(inputArray: Array[Int], sumToCheck: Int): Boolean = {
  val subtractList: ListBuffer[Int] = ListBuffer.empty
  var output = false
  for (i <- inputArray.indices) {
    if (subtractList.contains(inputArray(i))) {
      output = true
    }
    else {
      subtractList  = sumToCheck - inputArray(i)
      }
  }
  output
}

def checkTwoSumRec(inputArray: Array[Int], sumToCheck: Int): Boolean = {

  @tailrec
  def inner(input: Array[Int], subtractList: Array[Int] = Array.emptyIntArray): Boolean = {
    if (input.isEmpty) {
      false
    }
    else if (subtractList.contains(Option(input.head).getOrElse(0))) {
      true
    }
    else {
      inner(input.tail, subtractList :  (sumToCheck - Option(input.head).getOrElse(0)))
    }

  }

  inner(inputArray)

}

Could someone please give a hint if that's true?

CodePudding user response：

Few things here:

1. Both of those solutions are O(n^2) time complexity. Notice that contains on lists is O(n) and since you can use it n times, the complexity becomes O(n*n). A faster solution should use Map.
2. Tail recursion is usually better because it's a nicer way to write code i.e. it's harder to make mistakes. So recursion vs iteration is more about maintainability and readability of code and less about speed. (In Scala tail recursive functions are rewritten to while loops)
3. Option(input.head).getOrElse(0) is not safe. input.head throws a NoSuchElementException on empty list. So if you're sure that input is non-empty then simply use input.head and if you're not sure then use input.headOption and pattern match on it.