CODEWITHSUNDEEP
time-complexitybig-ospace-complexity
Phyllis Vance
Phyllis Vance

Reputation: 13

How to find time and space complexity of these algorithms?

I have problems in determining the time and space complexity of an algorithm. I am not sure if the following algorithm's time complexity is Theta(n/3) (which is Theta(n)), or it is Theta(log(n) base 3):

  def f1(x):
      m = len(x)
      found = False
      while m>=1:
         c = m - m/3*3
         if c==1: found=True
         m = m/3

I also have problems in computing the complexity of these algorithms:

def f2(x):
   found = False
   n = len(x)-1
   while n!=0 and not found:
      if x[n]==7: found=True
      else: n=n-1
   return found


def f3(x,i,j):
   if (i<j-1):
      k1 = (j-i+1)/3
      k2 = 2*k1
      f3(x,i,i+k1)
      f3(x,i+k1+1,i+k2)
      f3(x,i+k2+1,j)
      for k in range(i,j):
         print x[k]
   else:
      print x[i]

I think the f2() function's time complexity is Theta(n), but I have doubts.

Is there any formula for computing the complexity of an algorithm?

Thank you in advance.

Upvotes: 1

Views: 366

Answers (1)

Prashin Jeevaganth
Prashin Jeevaganth

Reputation: 1343

Time complexity for f1 is O(log m), log m(base 3) is actually log m (base 10)/ log 3(base 10), and hence we can exclude the constants. While Master Theorem might be required to find many time complexities, some can be found by tracing number of function calls or number of loops. For f1, the number of loops is dependent on m(the length of the sequence x according to your code). m is divided by 3 in every iteration so number of ways is log m.

You are right for f2's time.

Upvotes: 0

Related Questions