-1

I'm fairly new to Python, so I'm still not that good at determining Big O time complexities of some programs. I would like to ask for some help. Here are some code snippets that I had a hard time knowing what the Big O is, and what I think the Big O is:

Code 1: O(n)

def foo(n):
   i = 0
   k = 0
   for i in range(0,len(n)):
      for j in range(0,k):
         n[i] = k + 1
         k = 0
   k += 1

Code 2: I actually have no idea here

def bar(x,i,j,y):
   if j >= i:
      foo = (i+j) // 2
      if x[foo] == y:
         return foo
      elif x[foo] > y:
         return bar(x,i,foo-1,y)
      else:
         return bar(x,foo+1,j,y)
   else:
      return -1

Code 3: O(m)

def count(a,b):
   # Let len(a) = m
   # Let len(b) = n
   count = 0
   for char in a:
      if char in b:
         count += 1
   return count

And if you would, kindly drop some tips on finding the Big O of programs similar to these code snippets. Any help would greatly be appreciated. Thank you!

starglitter
  • 11
  • 2

1 Answers1

0

Code 1 Let N be the length of n. This code will be O(N) but it won't do anything since the inner for loop does iterate over range(0,0).

Code 2 Let N be the length of x. Supposed that i and j are in a range that list x has the index for. Worst case scenario is that y is not in x and j - i are as great as possible. That would take about O(j-i) which is no more than O(N). Thus on average, this process takes O(N) or less.

Code 3 If char in b take O(1) that might be the case but I don't think so. It might take O(n) so the algorithm is O(mn)

For a simple algorithm, just count the loop manually. If recurrence is in the algorithm, using a kind of equation and count how many times should it iterate may help. Here's related question: Determining complexity for recursive functions