Given that bar (n) runs in (logn) time, write a recurrence relation for the time taken...

Transcribed Image Text:

Given that bar (n) runs in (logn) time, write a recurrence relation for the time taken by function foo (): void foo(int n) { if (n < 1) return; for (int i = 0; i < n; ++i) for (int j=0; j < n; ++j) bar(n); foo(n / 2); for (int i = 1; i < n; i = 2) foo(n/ 2); } // foo() Given that bar (n) runs in (logn) time, write a recurrence relation for the time taken by function foo (): void foo(int n) { if (n < 1) return; for (int i = 0; i < n; ++i) for (int j=0; j < n; ++j) bar(n); foo(n / 2); for (int i = 1; i < n; i = 2) foo(n/ 2); } // foo()