Big-O Coding
pls answer only if u know Big-O!!
Note:
First code (left side):
- T(n-1) is NOT the answer.
Second code (right side)
- T (n/2) and T(x, y/2) is NOT the answer.
- O(n), O(1), O(b^2), O(c), O(a) are NOT the worst auxiliary cases.
![Consider the function below written in Python3:<br>Consider the function below written in Python3:<br>def foo(a, b=[1]):<br>def bar(x, y):<br>if a <= 1:<br>if y > 0:<br>return b<br>if (y % 2):<br>b_new = [b[i] + b[i+1] for i in range(len(b)-1)]<br>return bar(x, y >> 1) + bar(x, y >> 1) + x<br>return foo(a-1, [1] + b_new + [1])<br>return bar(x, y >> 1) + bar(x, y >> 1)<br>else:<br>return 0<br>The recurrence relation for foo(a, b) when a > 0 and assuming n is the length of b is:<br>а,<br>The recurrence relation for bar(x, y) when x, y > 0 is:<br>T(а, п) - Т(<br>+o(n<br>T(x, y) = 2<br>+0(1<br>T<br>What is the worst-case auxiliary space complexity of bar(, y)?<br>(Follow/use the same notes above)<br>Answer:<br>](https://s3.us-east-1.amazonaws.com/storage.unifolks.com/qimg-008/008_bnfrzj0-1x24g2ps.png)
Extracted text: Consider the function below written in Python3: Consider the function below written in Python3: def foo(a, b=[1]): def bar(x, y): if a <= 1:="" if="" y=""> 0: return b if (y % 2): b_new = [b[i] + b[i+1] for i in range(len(b)-1)] return bar(x, y >> 1) + bar(x, y >> 1) + x return foo(a-1, [1] + b_new + [1]) return bar(x, y >> 1) + bar(x, y >> 1) else: return 0 The recurrence relation for foo(a, b) when a > 0 and assuming n is the length of b is: а, The recurrence relation for bar(x, y) when x, y > 0 is: T(а, п) - Т( +o(n T(x, y) = 2 +0(1 T What is the worst-case auxiliary space complexity of bar(, y)? (Follow/use the same notes above) Answer: