Resources
An algorithmic benchmark tests data processing speed on chunks of size megabytes (), measuring runtimes in microseconds (). For , ; for , ; for , . Formulate a power-law conjecture for the runtime where is in gigabytes () and is expressed in seconds (). State the predicted runtime in seconds for a input size of .
Answer and steps
Final answer
(or ), yielding (or approximately ).
Steps
Identify the Power from the Benchmark Pattern
A power-law relationship has the form:
Examine how runtime changes as the input size scales:
- From to (doubling , ratio ):
- From to (doubling , ratio ):
Because doubling the input size consistently quadruples the runtime (), the power is: This indicates a quadratic relationship, .
Formulate the Power-Law Equation
With , the runtime model is:
Accounting for the benchmark scaling factor and unit conversions from megabytes to gigabytes () and microseconds to seconds, the calibrated coefficient is:
Thus, the power-law conjecture relating input size (in ) to runtime (in ) is:
Predict Runtime for an Input Size of
Substitute into the formulated power-law equation:
Expressed in scientific notation, the predicted runtime is (or approximately ).
Typical errors
01 The student forgets to convert the base units of megabytes to gigabytes and microseconds to seconds, formulating the power law directly in the original benchmark units.
Sample Student Work
Reviewed by ACEpath TeacherStep-by-Step Review
Walk Through It with Your Teacher- Step 1
- Step 2Correct
(or )
You took directly from the benchmark data without converting units. The problem requires to be measured in gigabytes () and in seconds (), so the leading coefficient must be recalibrated for these units.
- Step 3Correct
Your arithmetic calculation for correctly followed your formula, but the result is inaccurate because it inherited the uncalibrated coefficient from Step 2.
WHAT YOU DID WELL
Compliments from Your TeacherYou correctly calculated the ratio of consecutive runtime outputs to identify that doubling the input quadruples the runtime.
You accurately concluded that the exponent in the power-law model is .
THE ERROR
Where Your ACEpath Teacher Spotted the MistakeYou substituted the raw benchmark coefficient directly into the formula without adjusting for gigabytes and seconds.
WHY IT HAPPENED
ACEpath Teacher's DiagnosisOverlooking the required units specified in the model definition and assuming that raw data coefficients transfer directly across different unit scales.
REASONING PATH
Your ACEpath teacher’s suggested approach- Identify Target Units First
Always list the required units for both the independent variable () and dependent variable () before writing the final model equation.
Check whether the benchmark data is in and while the target equation requires and .
- Recalibrate the Leading Constant
When substituting scaled variables into , expand the conversion factor inside the power: .
Multiply or divide the raw coefficient by the appropriate unit scale factors before stating .
CORRECTED PATH
ACEpath Teacher's DemonstrationIn benchmark units, runtime is .
Convert input size: an input of equals .
Convert runtime units: calibrate the benchmark coefficient to obtain , giving (or ).
Substitute : .
and
02 The student converts microseconds to seconds but divides N by 1024 instead of multiplying when substituting N_MB in terms of N_GB.
Sample Student Work
Reviewed by ACEpath TeacherStep-by-Step Review
Walk Through It with Your Teacher- Step 1
- Step 2
- Step 3Correct
Since , a size of gigabytes contains megabytes. You divided by instead of multiplying.
- Step 4Correct
Because you divided by rather than multiplying by , your model coefficient is off by a factor of .
- Step 5Correct
This runtime prediction follows consistently from your incorrect power-law equation.
WHAT YOU DID WELL
Compliments from Your TeacherYou correctly identified the quadratic power from the benchmark data.
You correctly set up the conversion from microseconds to seconds.
THE ERROR
Where Your ACEpath Teacher Spotted the MistakeYou divided by when converting from gigabytes to megabytes, even though contains .
WHY IT HAPPENED
ACEpath Teacher's DiagnosisConfusing the unit equality with the algebraic relationship between the numerical variables: expressing a quantity in a smaller unit requires multiplying the numerical value by the conversion factor.
REASONING PATH
Your ACEpath teacher’s suggested approach- Check Unit Scale Direction
Converting a quantity to a smaller unit increases its numerical value, while converting to a larger unit decreases its numerical value.
Always substitute into equations calibrated in smaller units.
CORRECTED PATH
ACEpath Teacher's DemonstrationExpress input size gigabytes in megabytes: .
Substitute and into the benchmark equation: .
Simplify the coefficient or apply the calibrated model .
Evaluate at : .
, yielding
03 The student converts N from GB to MB linearly without squaring the conversion factor 1024 in the formula.
Sample Student Work
Reviewed by ACEpath TeacherStep-by-Step Review
Walk Through It with Your Teacher- Step 1
- Step 2Correct
When substituting into , the conversion factor of must also be squared: . You included only linearly, making your model coefficient too small.
- Step 3Correct
You correctly substituted and computed , but your final numerical answer is affected by the missing factor from Step 2.
WHAT YOU DID WELL
Compliments from Your TeacherYou correctly determined that doubling quadruples runtime, giving .
You correctly formulated the baseline equation in megabytes and microseconds.
You accurately calculated and correctly multiplied your derived coefficient by .
THE ERROR
Where Your ACEpath Teacher Spotted the MistakeYou converted gigabytes to megabytes using a single linear factor of rather than squaring inside the quadratic term.
WHY IT HAPPENED
ACEpath Teacher's DiagnosisWhen a variable inside a power-law expression undergoes a unit conversion , the conversion constant must also be raised to the power : .
REASONING PATH
Your ACEpath teacher’s suggested approach- Square the Entire Substitution
Write parentheses around the complete substitution before distributing the exponent to both and .
- Dimensional Scaling Check
If a quantity scales with degree , its unit conversion factor scales with degree .
Verify that converting units for an term scales by the square of the conversion ratio, not the linear ratio.
CORRECTED PATH
ACEpath Teacher's DemonstrationSubstitute into the squared term: .
Calibrate the leading coefficient to express runtime in seconds: , giving .
Evaluate for : .
(or ), yielding
Lock it in
When transforming a power-law relation so that input is measured in a unit times larger (), how does the new coefficient change?
The new coefficient becomes because substituting gives .
Similar question
An algorithm takes for and for . Express the power-law model where is in megabytes () and is in seconds ().
Answer
. Key steps: . In benchmark units, . Substituting yields . Converting to seconds divides by , giving .
A database query has runtime for records and for records. Formulate with measured in thousands of records () and in seconds. Then find for .
Answer
and . Key steps: doubling multiplies runtime by . At , runtime is . Thus . For , .
A matrix factorization benchmark records runtimes: and , where is the matrix dimension. Construct a runtime model with in seconds. What is the predicted runtime in seconds for ?
Answer
and . Key steps: . Each doubling scales time by . From to is two doublings (), so runtime scales by . (or using seconds directly: ).