Heena Agarwal

Ranch Hand

Posts: 262

4

posted 3 years ago

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.

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

73

Heena Agarwal

Ranch Hand

Posts: 262

4

posted 3 years ago

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:

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.

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

Ulf Dittmer

Rancher

Posts: 42970

73

posted 3 years ago

- 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

posted 3 years ago

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

- 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

posted 3 years ago

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

Now I know.

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 thelogof 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.