2

what is the Big O notation for that two algorithms:

def foo1(n):
    if n > 1:
        for i in range(int(n)):
            foo1(1)
        foo1(n / 2)

def foo2(lst1, lst2):
    i = 1
    while i < max(len(lst1), len(lst2)):
            j = 1
            while j < min(len(lst1), len(lst2)):
                j *= 2
            i *= 2

I thought that foo1 run time complexity is O(n) because in that case if I see the for loop I can do that:

T(n) = O(n) + O(n/2) <= c*O(n) (c is const) for all n.

is that right ?

and I cant calculate the run time of foo2 can some one help me to know to do that.

thanks...

Mohammad Jaber
  • 63
  • 9

1 Answers1

2

  1. The number of operations T(n) is equal to T(n/2) + n. Applying the Master theorem we get T(n) = O(n). In simple terms there are n + n/2 + n/4 + ... + 1 operations that are less than 2*n and is O(n).

  2. The inner loop does not depend on the outer loop, so we can treat them independently. T(n) = O(log(maxlen) * log(minlen)).

DAle
  • 8,990
  • 2
  • 26
  • 45
  • I except with you in the run-time of foo2 thank you for that, it is logical here. but can you explain way you multiply T(n / 2) with 2. what is the 2 here. thanks. – Mohammad Jaber Oct 17 '17 at 13:35
  • @MohammadJaber, that's my mistake, I'll change the answer – DAle Oct 17 '17 at 13:36
  • ok, but thanks for you, I dont think that the Master theorem will help me here but now I learn that that it will help me in that case ... thanks – Mohammad Jaber Oct 17 '17 at 13:40