Data Structures and Algorithms - Performance Analysis of Algorithms and Recurrences
- Option : C
- Explanation : Use binary search in the array of number from 1 ........ n to check cube of the number matches n (i.e. a[i]* a [i]* a [i] = = n). option (C) is true
- Option : C
- Explanation : The best complexity in worst case for any comparision based sorting technical cannot be less then nlogn.
- Option : C
- Explanation : Given program fragment in Pseudo language is
x = m ;
y = 1 ;
while (x – y > e)
x = (x + y) /2 ;
y = m/x ;
}
Print (x)
This program will find out the square root of m,
suppose that m = 2
as x – y = 0 exit from loop hence print 1.414 which is root of 2.X- Y X Y 1st looping 2 3/2=1.5 2/1.5=1.33 2nd looping .16 (1.5+1.3)/2 = 1.415 2.0/1.415 = 1.413 3rd looping 0.02 1.414 1.414 4th looping 0
- Option : C
- Explanation : Case I :– if A = 0 0 0 0 0 0 0 ... then always else part is execute so f (wanter) where counter = 0 is executed n times. As given in clvestion complexity of f(o) is O (1) So O (1) + O (1)..... b times ⇒ O (n) Case II : if A = [1, 1,.................1] the loop execute n time and only if statment is executed hence complexity is O (n). Case III : if A = [1,0,1,0,1,0..........] or A = [0,1,0,1,0,1...................] or any other case. Both if and else is executed but every time when else part is executed counter is again set to O. Hence complexity is O (n).
- Option : D
- Explanation : Recurrence relation for function is T (n) = 2 T (n – 1) + 1 = 2 [2T (n–2) + 1] + 1 = 4 T (n–2) + 2 + 1 = 4 [2T (n–3)+1] + 2 + 1 = 23T (n–3) + 22 + 2 + 1 2k T (n–k) + 2k-1 + ---2+1 put n–k = 1 So 2n-1 T (1) + 2n-2 + ----- 2 + 1 ⇒ 2n-1 + 2n-2 + --- 2 + 1 ⇒ 2n-1 ⇒ O (2n).
