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?

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

Joined: Dec 25, 2013
Posts: 262

4

posted

0

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: 262

4

posted

0

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

Joined: Mar 22, 2005
Posts: 42959

73

posted

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 :-)

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: 262

4

posted

0

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)