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?
Few things here:
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
.while
loops)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.