Nsryjdtyk

Working on the efficiency of the Big-O notation i find myself in a series of doubts with the elaboration of a type of code that works in time O(n log n), to perform the next task:

· find the minimum number of a list (the order of the factors is not important)

· alternative to using... min method

I know that the in this magnitude means time goes up linearly while the n goes up exponentially (thanks to other users)

To understand it this magnitude, for exapmle i have this code.

 def x(my_list):



     n = len(my_list)

     print(my_list)



     if n <= 1:

         print("return")

         return 0



     return x(my_list[:n // 2]) + x(my_list[n // 2:])



print(x([2, 3, 4, 5, 6, 7]))

Also works with lists, but it does not do what i want.
This returns once for each element in the list O(n)...It then also implements a bisection search O(log n) == O(n log n)

Thanks :)

Answer to the question that is asked in the title:

def min_of(lst):

    if len(lst) <= 2:

        return lst[0] if lst[0] < lst[-1] else lst[-1]

    a = min_of(lst[len(lst)/2:])

    b = min_of(lst[:len(lst)/2])

    return a if a < b else b

UPDATE

Sorry, this is O(n) method

Is your list sorted? Then to find the minimum value it's just the first element of the list: my_list[0]. This is O(1) (constant time - no looping required).

Is your list not sorted? Then you'll have to scan through every single value in the list to determine which one is the smallest compared to the rest. This is at minimum O(n) (note that O(n) is more efficient than O(nlogn)).

current_min = my_list[0]

for element in my_list:

    if element < current_min:

        current_min = element