1

I have the following function:

def pascal_triangle(i:int,j:int):
    j = min(j, i-j + 1)
    if i == 1 or j == 1:
        return 1
    elif j > i or j == 0 or i < 1 or j < 1:
        return 0 
    else:
         return pascal_triangle(i-1,j-1) + pascal_triangle(i-1,j)

The input value for j has the following constraint:

1<=j<=i/2

My computation for the time complexity is as follows:

f(i,j) = f(i-1,j-1) + f(i-1,j) = f(i-n,j-n) + ... + f(i-n,j)

So, to find the max n, we have:

i-n>=1
j-n>=1
i-n>=j

and, since we know that:

j>=1
j<=i/2

The max n is i/2-1, so the time complexity is O(2^(i/2-1)), and the space complexity is the maximum depth of recursion(n) times needed space for each time(O(1)), O(2^*(i/2-1)).

I hope my calculation is correct. Now my concern is that if i is odd, This number is not divisible by 2, but the terms of function must be an integer. Therefore, I want to know should I write the time complexity like this:

The time complexity and space complexity of the function are both:

O(2^(i/2-1)) if i is even
O(2^(i/2-0.5)) if i is odd
BrokenBenchmark
  • 18,126
  • 7
  • 21
  • 33
Carlos
  • 167
  • 1
  • 2
  • 14

1 Answers1

2

At a first glance, the time and space analysis looks (roughly) correct. I haven't made a super close inspection, however, since it doesn't appear to be the focus of the question.

Regarding the time complexity for even / odd inputs, the answer is that the time complexity is O(sqrt(2)^i), regardless of whether i is even or odd.

In the even case, we have O(2^(i / 2 - 1)) ==> O(1/2 * sqrt(2)^i) ==> O(sqrt(2)^i).

In the odd case, we have O(2^(i / 2 - 0.5)) ==> O(sqrt(2) / 2 * sqrt(2)^i) ==> O(sqrt(2)^i).

What you've written is technically correct, but significantly more verbose than necessary. (At the very least, it's poor style, and if this question was on a homework assignment or an exam, I personally think one could justify a penalty on this basis.)

BrokenBenchmark
  • 18,126
  • 7
  • 21
  • 33
  • It's not technically correct. It contains constant terms and factors. It's wrong. They should be removed. – user207421 Mar 21 '22 at 05:51
  • 1
    @user207421 What's wrong? You can't mean unnecessary terms/factors which don't make a difference. – Kelly Bundy Mar 21 '22 at 08:43
  • @KellyBundy Yes I can. That is exactly what I do mean. Big-O notation doesn't have them. Any Big-O expression containing them is therefore incorrect. – user207421 Mar 21 '22 at 22:17
  • 2
    No, [there is nothing in the formal definition of Big-O that prevents constants from appearing](https://stackoverflow.com/a/25777739/17769815). It's poor style, but it doesn't affect correctness. – BrokenBenchmark Mar 21 '22 at 22:20
  • @BrokenBenchmark You cannot cite a Stack Overflow answer as a normative reference or 'formal definition'. – user207421 Mar 21 '22 at 23:40
  • 2
    @user207421 Sure, how about definitions from [NIST's Dictionary of Algorithms and Data Structures](https://xlinux.nist.gov/dads/HTML/bigOnotation.html), [MIT's 6.042](https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-042j-mathematics-for-computer-science-spring-2015/readings/MIT6_042JS15_Session24.pdf), or [Rice University's COMP310](https://www.clear.rice.edu/comp310/course/design/big_o.html)? None of these definitions prohibit constant terms from being used in big-O notation. – BrokenBenchmark Mar 21 '22 at 23:58
  • 2
    @user207421 The fact that O(2n+1) = O(n) is due to the functions n and 2n+1 belonging to the same class of functions. It does not mean that O(2n+ 1) is somehow wrong. – Berthur Mar 22 '22 at 21:53