Provide tight asymptotic bounds (i.e. (·)) on the worst case running times of th
ID: 3877636 • Letter: P
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