-1

can someone tell me what is the complexity in the function and why please? Thanks

def func1(n):
    if n==0:
        return (1)
    if n==1:
        return (1)
    if n==2:
        return (2)
    return (n*func1(n-3))

n=int(input())
func1(n)

I think the complexity is: "O(nlog n)"

Janez Kuhar
  • 3,705
  • 4
  • 22
  • 45
Raz Elbaz
  • 1
  • 1
  • 1
    For all positive `n`s, there will be at most `n / 3` iterations of the loop (you have a *tail recursion*). That, however, is still linear time - O(n). – Janez Kuhar Jul 24 '21 at 21:50
  • 2
    @JanezKuhar, this is *not* tail recursion (but near). The last operation isn't a call to `func1()`, it is the multiplication by `n`. – vonbrand Jul 24 '21 at 21:57
  • 1
    You would typically write `return 1`, rather than `return (1)`. – jarmod Jul 24 '21 at 22:04

1 Answers1

0

The time complexity of the function is O(n) because n - 3 is linear. It would be O(logn) if it was a dividing operation. For further explanation, you can refer to this.

P.S. multiplication with n itself does not affect the given parameter in each recursive call therefore, it does not affect time complexity at all.

Rarblack
  • 4,559
  • 4
  • 22
  • 33