Big-O

c) [5 marks] Read over function xgcd, which calculates the extended gcd(a, b), below: 1 def xgcd (n, m): sl, so, t1, to, r1, ro =0, 1, 1, 0, m, n while ri 0: 2 quotient = r0 // r1 ro, r1 - r1, ro - quotient. ri, ro - quotient * ri s0 , s1 = s1, so - quotient * s1 tO, t1 = t1, t0 - quotient * t1 return (ro, so, to) Let the input size be a. Assume that the loop body, lines 4-7, is 1 "step". Prove that the runtime of xged, RTxged E O(1g a). Hint: Can you show that every two iterations of the loop reduces r0 by at least half? c) [5 marks] Read over function xgcd, which calculates the extended gcd(a, b), below: 1 def xgcd (n, m): sl, so, t1, to, r1, ro =0, 1, 1, 0, m, n while ri 0: 2 quotient = r0 // r1 ro, r1 - r1, ro - quotient. ri, ro - quotient * ri s0 , s1 = s1, so - quotient * s1 tO, t1 = t1, t0 - quotient * t1 return (ro, so, to) Let the input size be a. Assume that the loop body, lines 4-7, is 1 "step". Prove that the runtime of xged, RTxged E O(1g a). Hint: Can you show that every two iterations of the loop reduces r0 by at least half