@giga4089513387, you are correct that there are 2N function calls. However, it is not just the number of calls to the function that is important, but also the work which is done within the function at each call…

*But*, as far as I can tell, the work in this case involves finding the value of a list at a certain index (constant time), setting a key:value pair for a dictionary (constant time), and calling a function twice (constant time). So, I don’t see that there is anything there to increase the time complexity beyond O(N).

To see how the time varies with input, I used the Python module timeit. Here are the results I got, using sorted lists of lengths increasing from 10 to 10**7 by a factor of 10 each time (source code below).

```
build_bst Time for n = 10 is 0.00011 (10 runs)
Current time / prior time = 0.00010709999999997111
build_bst Time for n = 100 is 0.00104 (10 runs)
Current time / prior time = 9.702147525679695
build_bst Time for n = 1000 is 0.01082 (10 runs)
Current time / prior time = 10.415359445673952
build_bst Time for n = 10000 is 0.12183 (10 runs)
Current time / prior time = 11.256648125219485
build_bst Time for n = 100000 is 1.16860 (10 runs)
Current time / prior time = 9.59236108488979
build_bst Time for n = 1000000 is 12.27396 (10 runs)
Current time / prior time = 10.503123264751892
build_bst Time for n = 10000000 is 121.69054 (10 runs)
Current time / prior time = 9.914530073437673
```

It seems pretty evident that the average running time for each list length is very nearly 10 * the time for the previous list; i.e., the function certainly appears to run in linear time.

I’d like to see some more comment on this one!!

The above data are the output from the code below:

```
# https://docs.python.org/3/library/timeit.html#examples
# Here is the function being tested
def build_bst(my_list):
if my_list == []:
return "No Child"
middle_idx = len(my_list)//2
middle_value = my_list[middle_idx]
# print("Middle index: {}".format(middle_idx))
# print( "Middle value: {}".format(middle_value))
tree_node = {'data': middle_value}
tree_node['left_child'] = build_bst(my_list[:middle_idx])
tree_node['right_child'] = build_bst(my_list[middle_idx + 1:])
return tree_node
# Here is the function that will be passed to timeit
f1 = build_bst
f1_name = "build_bst"
# Here is the timing run
if __name__ == "__main__":
import timeit
import random
import math
runs = 10
t_2, i_2 = 1, 1
base = 10
for i in range(1, 8):
in_lst = [j for j in range(base**i)]
t_1 = timeit.timeit("f1(in_lst)", number = runs, globals = globals())
i_1 = i
print("{} Time for n = {} is {:.5f} ({} runs)".format(f1_name, base**i_1, t_1, runs))
print(" Current time / prior time = {}".format(
t_1/t_2, base**i_1/base**i_2))
t_2 = t_1
i_2 = i_1
```