0

I am very new to time complexities and I couldn't find a detailed explanation on how to calculate the T(n) of a given algorithm.

def search(k, lst_1, lst_2):
   n = len(lst_1) + len(lst_2)
   
   for i in range(0, math.ceil(n/2)):
       if lst_1[i] == k:
          return 2 * i

   for j in range(0, math.floor(n/2)):
       if lst_2[j] == k:
          return 2 * i + 1

   return -1

This is not a "do my hw" question. I actually want to learn how to calculcate the T(n) of this algorithm.

Onur-Andros Ozbek
  • 2,998
  • 2
  • 29
  • 78
  • It is probably irrelevant to the time complexity, but I think your second return should be `2 * j + 1` – nonDucor Jun 26 '22 at 17:19
  • 1
    For finding out examples, youtube is there. There are tremendous free resources and free examples which you can solve. Just check the views and go with the highest views. Low views may tend to have wrong explainations! – Jimut123 Jun 26 '22 at 17:27

1 Answers1

2

T(n) is used for finding out time complexities of a program. The more the T(n), the slower the program.

Here

def search(k, lst_1, lst_2):
   n = len(lst_1) + len(lst_2) # Takes O(1) time which is constant, since length calculation will be done in constant time
   
   for i in range(0, math.ceil(n/2)): # say this takes O(n/2) time, but since 1/2 is a constant, we don't take it. Hence we write it as O(n) time complexity
       if lst_1[i] == k:
          return 2 * i

   for j in range(0, math.floor(n/2)):# Similarly, this too takes O(n/2) time, but since 1/2 is a constant, we don't take it. Hence we write it as O(n) time complexity
       if lst_2[j] == k:
          return 2 * i + 1

   return -1

So, finally your program takes O(n) time, since O(n) + O(n) + O(1) is equivalent to O(2n) which is equivalent to O(n), since 2 is a constant and O(1) is negligible. You can practice a lot of example and probably see the wikipedia for initial definitions https://en.wikipedia.org/wiki/Time_complexity

Jimut123
  • 474
  • 5
  • 14
  • 1
    How can we represent O(n) as an expression for both the worst-case and best-case running times (or execution time) T(N)? – Onur-Andros Ozbek Jun 26 '22 at 17:27
  • In calculating the time complexity, we generally go with worst case complexities. We are not going for the best case complexity here. Best case would be O(1) here. – Jimut123 Jun 26 '22 at 17:28