wood burning stoves 2.0*
The moose likes General Computing and the fly likes How can y intercept of an equation be negative in this case? Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Engineering » General Computing
Bookmark "How can y intercept of an equation be negative in this case?" Watch "How can y intercept of an equation be negative in this case?" New topic
Author

How can y intercept of an equation be negative in this case?

Heena Agarwal
Ranch Hand

Joined: Dec 25, 2013
Posts: 261
    
    4
Hi,

I was going through the following video on Coursera

https://class.coursera.org/algs4partI-004/lecture/11

on analysis of algorithms.

So let us say that we have a brute force (sort of ) computation of following nature in our code...



So this must give brute force algorithms like performance for large input size ( n is the input size ).

In the video, Wayne explains that if we observe the performance of such an algorithm with various input sizes and then draw these points on a graph that has log base 2 of input size on the x axis and log base 2 of the running time on the y axis, we get a straight line with a steep slope of 3. This part is easy to visualize if I just consider that this is almost like brute force and that for large inputs the running time will be proportional to N^3.

But if I were experimenting this algorithm with real values, I'd solve it as follows.

lg (T(N)) = m(lg N) + C

(The above equation is my own variant of Wayne's equation --> lg (T(N)) = b lg N + c )

( y = mx + c. m is the slope, c is the y intercept .. y = lg (T(N)), T(N)= running time of the program, N is the input size, lg = log base 2 )

According to the observed data, Wayne says that he got m= 2.999 and c= -33.2103. I don't understand how c can have a negative value. We know that lg 1 = 0.

How is a negative value possible? For x =0, y should always be positive cause a program requires some minimum positive time to run, no matter how small is the input size.

So would someone know how C can have a negative value?

Thanks.
Ulf Dittmer
Marshal

Joined: Mar 22, 2005
Posts: 42294
    
  64
What that equation does for small X is irrelevant ; it's asymptotically correct for large X. And for large X the constant c is dominated by m*x.


Ping & DNS - my free Android networking tools app
Heena Agarwal
Ranch Hand

Joined: Dec 25, 2013
Posts: 261
    
    4
Ulf Dittmer wrote:What that equation does for small X is irrelevant ; it's asymptotically correct for large X. And for large X the constant c is dominated by m*x.


Yeah, the y intercept can be ignored for large inputs. But I thought that the negative value of y intercept out there should be wrong cause I think it should have a positive value. But it's empirical analysis. So it's probably not that simple, straight 1+1 = 2 math.

But I should probably ignore this because of the reason you mentioned. I was just ... thinking.

I thought about it for about 10 minutes. So I thought it necessary to make the rest of the world also think about it. :-) Don't mind...

Edit:
it's asymptotically correct for large X.


Sorry I didn't read that part correctly. On reading your response again, I sort of get it now... it must a fair approximation.

Thank you, Ulf.
Heena Agarwal
Ranch Hand

Joined: Dec 25, 2013
Posts: 261
    
    4
And I edited my post by mistake.


Edit : And I could replace it. I'm just done with today's studies.. So no more of this. I promise.
Ulf Dittmer
Marshal

Joined: Mar 22, 2005
Posts: 42294
    
  64
I like this stuff. Of course, I have an advanced degree in computer science, where you spend entire semesters dealing with topics like Big O notation, and whether some problem is NP complete. (Which may sound irrelevant for any practical purpose, but it help you assess whether a brute force approach may or may not be feasible - which brings us full circle to the original question :-)
Mike Simmons
Ranch Hand

Joined: Mar 05, 2008
Posts: 3018
    
  10
Heena Agarwal wrote:Yeah, the y intercept can be ignored for large inputs. But I thought that the negative value of y intercept out there should be wrong cause I think it should have a positive value.

No, there's nothing wrong with a negative value here. It might even be exactly correct. Remember, the Y value in this case is not time (which presumably should not be negative), but the log of time. A log can certainly be negative, if you take the log of a number between 0 and 1 (exclusive). So this just means your Y intercept represents a value of less than 1 second (or whatever the time unit is).
Heena Agarwal
Ranch Hand

Joined: Dec 25, 2013
Posts: 261
    
    4
Mike Simmons wrote:
Heena Agarwal wrote:Yeah, the y intercept can be ignored for large inputs. But I thought that the negative value of y intercept out there should be wrong cause I think it should have a positive value.

No, there's nothing wrong with a negative value here. It might even be exactly correct. Remember, the Y value in this case is not time (which presumably should not be negative), but the log of time. A log can certainly be negative, if you take the log of a number between 0 and 1 (exclusive). So this just means your Y intercept represents a value of less than 1 second (or whatever the time unit is).


Thanks, Mike. Following is what I was missing.. I get it now.

Mike Simmons wrote:Remember, the Y value in this case is not time (which presumably should not be negative), but the log of time. A log can certainly be negative, if you take the log of a number between 0 and 1 (exclusive)


Now I know.
 
It is sorta covered in the JavaRanch Style Guide.
 
subject: How can y intercept of an equation be negative in this case?