1. Consider the following algorithms: algorithm DOSOMETHING(A, m, n): if n - m = 0 then _ return else for im to n do Ai,j← Aj,i for j = = m to n do AijAij+i+j DOSOMETHING(A, m + 1, n) algorithm DOSOMETHINGELSE(A, m, n): if n -m= ■ return else 0 then for im to n do | Aij← Aji+i P← (n - m)/3 DOSOMETHINGELSE(A, m, m + p) DOSOMETHING ELSE (A, m+p+1, m+2p) DOSOMETHINGELSE(A, m + 2p + 1, n) (a) Write down the recurrence relation for the time complexity of each algorithm. Justify your answer fully. (b) Solve the two recurrence relations you just developed and thus give the running time of each algorithm in ☺ notation. Provide full and formal solutions. Note however that I am only asking for the complexity and so you do not need to worry about constants (unless they are part of the formal solution).

1. Consider the following algorithms: algorithm DOSOMETHING(A, m, n): if n - m = 0 then _ return else for im to n do Ai,j← Aj,i for j = = m to n do AijAij+i+j DOSOMETHING(A, m + 1, n) algorithm DOSOMETHINGELSE(A, m, n): if n -m= ■ return else 0 then for im to n do | Aij← Aji+i P← (n - m)/3 DOSOMETHINGELSE(A, m, m + p) DOSOMETHING ELSE (A, m+p+1, m+2p) DOSOMETHINGELSE(A, m + 2p + 1, n) (a) Write down the recurrence relation for the time complexity of each algorithm. Justify your answer fully. (b) Solve the two recurrence relations you just developed and thus give the running time of each algorithm in ☺ notation. Provide full and formal solutions. Note however that I am only asking for the complexity and so you do not need to worry about constants (unless they are part of the formal solution).