I would appreciate some help in figuring out the time complexity of the solution for Search Range problem from leetcode which involves recursion and DnC algorithm.
I am not sure whether it is O(N) or O(NlogN) and why?
func searchRange(nums []int, target int) []int {
if (len(nums) == 0) {
return []int{-1, -1}
}
return helper(nums, target, 0, len(nums) - 1)
}
func helper(nums []int, target, start, end int) []int {
res := []int {-1, -1}
if (nums[start] > target || nums[end] < target || start > end || (start == end && nums[start] != target)) {
return res
}
if (start == end) {
res[0] = start
res[1] = end
return res
}
mid := (start + end) / 2
res1 := helper(nums, target, start, mid)
res2 := helper(nums, target, mid + 1, end)
if (res1[0] == -1) {
return res2
}
if (res2[0] == -1) {
return res1
}
res[0] = res1[0]
res[1] = res2[1]
return res
}