Anonymous
BAN USERone more method is using signal and systems method the Fibonacci series satisfies the equation
x(n)-x(n-1)-x(n-2)=0
taking z transforms on both side
X(z)-z^-1X(z)-z^-2X(z)=0
simplifying
X(z)(z^2-z-1)=0
finding roots of the equations
r1=(1+sqrt(5))/2 and r2=(1-sqrt(5))/2
therefore solution is of the form
x(n)=a*(r1)^n+b*(r2)^n
where a and b are constants
but we know that x(0)=0 and x(1)=1 substituting initial condition we get
x(n)= r1^(n+1)/sqrt(5)
which is not integer by rounding it to nearest integer we can find x(n) with O(1) complexity...
the question here is how we can reduce the complexity... if we compute the x^y by normal method the complexity is O(y)... to reduce the complexity we can use binary weighted power computation method in which complexity is O(logy)..
ans=1;
square=x;
if(y==0)
return 1;
while(y!=0)
{
if(y%2)
ans=ans*square;
square=(square*square)%z;
y=y/2;
if(ans>z)
ans=ans%z;
}
return ans;
by making some modification in above method we can search for an element. that is once the slop of mid_point is checked if that is + ve check whether key is between start_point and mid_point if it is in between then key found if not we found that key is not in increasing part... it should be in decreasing part... same applies for decreasing part also... once the key not found we can repeat the dividing part till we get the key in between other part of the list... the complexity is still O(log(n))...
- Anonymous July 19, 2013let us consider the reading as reading of some curve.. according to the given data first part has +ve slop and second part has negative slop.(i.e a[i+1]-a[i] is +ve for first half and -ve for second half) to find the pivot in log(n) complexity first consider start_point and end_point element then find mid_point (start_point+end_point)/2 find its slop if it is +ve replace start_point with mid element if -ve replace end_point with mid_point repeat the procedure updating start_point and end_point finally you end up with a pivot point(with log(n) complexity). once pivot is found perform binary search again worst case complexity is log(n). overall complexity is 2log(n) or O(log(n))
- Anonymous July 19, 2013
considering lines, not line segment we can have 3 cases for a given pair of lines
- Anonymous July 29, 2013y=m1*x+c1
y=m2*x+c2
case1) lines do not intersect if both the lines are parallel to each other that is
m1=m2 and c1 != c2
case2)lines are collinear when m1=m2 and c1= c2 in this case there will be more than one point where line intersects(all the points on the line infinite)
case3) for all other case there will be exact one intersection point
xs=(c1-c2)/(m2-m1) and ys=m1*xs+c1 where (xs,ys) is intersection point..