Homework Help is Here – Start Your Trial Now!
Engineering
Data Structures and Algorithms
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).

icon
Related questions
Question
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).
Transcribed Image Text: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).
Expert Solution
steps

Step by step

Solved in 2 steps

SEE SOLUTIONCheck out a sample Q&A here
Blurred answer
Similar questions