Win a copy of Head First Agile this week in the Agile forum!
programming forums Java Java JSRs Mobile Certification Databases Caching Books Engineering OS Languages Paradigms IDEs Build Tools Frameworks Products This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
Sheriffs:
Saloon Keepers:
Bartenders:

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

Heena Agarwal
Ranch Hand
Posts: 262
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
Rancher
Posts: 42972
73
• 1
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.

Heena Agarwal
Ranch Hand
Posts: 262
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
Posts: 262
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
Rancher
Posts: 42972
73
• 1
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
Posts: 3090
14
• 1
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
Posts: 262
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.