Provide tight asymptotic bounds (i.e. (·)) on the worst case running times of th

Question

Provide tight asymptotic bounds (i.e. (·)) on the worst case running times of the following two procedures.

(a)

1: procedure BackForwardAlg(n)
2: if n 10 then
3:      return n
4: if n even then
5:      return BackF orwardAlg(n/2)
6: else
7:      return BackF orwardAlg(n + 3)

(b)
1: procedure RecursiveAlg(A[1 . . . n])
2: if n == 1 then
3:      return False
4: mid = dn/2e
5: for i = 1 to mid do
6:      for j = mid + 1 to n do
7:           if A[i] == A[j] then
8:                return True
9: return (RecursiveAlg(A[1 . . . mid]) || RecursiveAlg(A[mid + 1 . . . n]))

(c) (2 bonus points) Give a one sentence description of what RecursiveAlg does.

Explanation / Answer

a)

the worst case running time is :O(log n)

best case also Omega(log n)

explanation:

if n is even and greater than 10 , it divides n by 2 up to , n is less than or equal to 10, means every time n is reduced by half....so complexity would be log n

if n is odd than 3 is added to it...then it will become even...again above case is repeated.

b)the worst case complexity is O(n^2 logn)

explanation:

in worst case

if list size is n,

then inner loops will run for n/2 *n/2 times.. (n^2)/4

//if condition is not satisfied  then// if A[i] == A[j] then

then after next recursive calls they run for

n/4*n/4

on a complete level of calling they will be(recursive tree)

n/4*n/4+n/4*n/4+n/4*n/4+n/4*n/4 = (n^2)/4

in next level

n/8*n/8+n/8*n/8+n/8*n/8+n/8*n/8+n/8*n/8+n/8*n/8+n/8*n/8+n/8*n/8 = (n^2)/4

..

so... total their will be logn levels

hence the complexity is O(n^2 logn)

c)

RecursiveAlg checks whether at least one pair of numbers that are equal or not in given array...

if they exist then it return true

otherwise false

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.