|
URGENT!! Algorithm questions
Link |
by killerdevil
on 2011-09-11 08:55:20 (edited 2011-09-11 08:56:06)
|
|
for each of the following algorithm, give an asymptotic notation for the number of times which the statement x=x+1 is executed: i=2 while (i < n){ i=i*i x=x+1 } ans: O(lg lg n).... but i cannot get this answer... -------------------------------------------- also for recursive algorithm i have some enquiries: example: Algorithm Q(n) Input: positive integer n if n= 1 return 1 else return Q(n-1) + 2*n-1 my ans: T(n) = T(n-1)+1 . . = T(1) + n - 1 = n-1 = O(n) therefore this is my question, set up a recurrence relation for the number of multiplications made by the algorithm and solve it Algorithm S(n) //input: A positive integer n //output: the sum of the 1st n cubes if n=1 return 1 else return S(n-1)+n*n*n what is the Big-O for the above algorithm? how do i even start it?> T(n) = T(n-1)+ ??? and if the question was "S(n-1)*n*n*n" T(n) = T(n-1)+ ???
asd
|
|
Re: URGENT!! Algorithm questions
Link |
by
on 2011-09-11 17:26:12 (edited 2011-09-11 17:32:53)
|
|
Your algorithm for the sum of the first n cubes is O(n) because the recursive argument decrements from n down to 1. In other words, the argument of the function is not data-dependent on he return value of previous iterations, so the n*n*n part is ignored for calculating Big-O notation. 
|