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