Students
Teachers & SchoolsStudents
Teachers & SchoolsAPCS: Standard Algorithms Drill 2, Problem 1. How much slower is InefficientSum than EfficientSum in the best case for an array of n elements?
AP Computer Science | Standard Algorithms |
Language | English Language |
Standard Data Structures | Primitive data types (int, boolean, double), Strings, Classes, Lists, Arrays (1-dimensional and 2-dimensional) |
case for an array of n elements right here in
the rays list go all right here your potential answers
How many times slower like a rap song All right
well to answer this one we'll have to figure out
how both methods work to see exactly what would make
one of them less efficient than the other so for
efficient Some were creating a loop that begins with its
iterated at one and adds the contents of each following
array element to array in deck zero until we reach
the end In effect index zero becomes the running total
As we travel through the array makes sense and it's
pretty efficient just like the name says inefficient Some creates
a separate variable toe hold are running total then visits
each element of the array as we had done before
but here's the univision part while the value of the
current array element is greater than zero It subtract one
from it and adds one to the some variable Then
it checks it again and again and again And i
will keep doing this until the array element here is
zero So often injure in the array Had a value
of say fifty We'd have to complete this process fifty
times If an imager were a million six hundred four
thousand two hundred ninety three Well yeah inefficient is the
right word for it The difference is a bit like
someone opening a can of corn and eating each nibble
it one by one versus more standard practise of opening
the can and chugging the entire thing right there in
a sec It's the new mcdonald's product It's really cool
and fried Okay from this we can tell that the
larger the values aaron the array the larger the kansas
corn would be and the longer inefficient some would take
But this question is asking for the best case scenario
And by far the best cases faras inefficient Some is
concerned would be in a ray full of zeros It
could be enormous Hundreds of thousands of zeros and we'd
zip right through it Practically the same speed as efficient
son because we'd be avoiding that tedious wild loop entirely
The result in that best all zero case is that
bullet methods would run at the same speed or at
least at such close speeds that it would be difficult 00:02:22.83 --> [endTime] to accurately measure the difference That'll make our answer