2. (10 points) Describe in a few words what the algorithm Foo does and what the...

 

Transcribed Image Text:

2. (10 points) Describe in a few words what the algorithm Foo does and what the algorithm Bar does. Analyze the worst-case running time of each algorithm and express it using "Big-Oh" notation. Input: two integers, a and n Output: ? 1: function Foo(a, n) Input: two integers, a and n Output: ? 1: function BAR(a, n) 2: k0 2: k+n 3: b1 3: b+1 4: while kn do 4: ca 5: kk+1 5: while k 0 do 6: bb*a 6: 7: return b 7: 8: if k mod 20 then k+k/2 CCC 9: else 10: kk 1 11: bb*c 12: return b 2. (10 points) Describe in a few words what the algorithm Foo does and what the algorithm Bar does. Analyze the worst-case running time of each algorithm and express it using "Big-Oh" notation. Input: two integers, a and n Output: ? 1: function Foo(a, n) Input: two integers, a and n Output: ? 1: function BAR(a, n) 2: k0 2: k+n 3: b1 3: b+1 4: while kn do 4: ca 5: kk+1 5: while k 0 do 6: bb*a 6: 7: return b 7: 8: if k mod 20 then k+k/2 CCC 9: else 10: kk 1 11: bb*c 12: return b