ShmoopTube

Where Monty Python meets your 10th grade teacher.

Search Thousands of Shmoop Videos

AP Computer Science 2.1 Standard Algorithms 432 Views


Share It!


Description:

APCS: Standard Algorithms Drill 2, Problem 1. How much slower is InefficientSum than EfficientSum in the best case for an array of n elements?

Language:
English Language

Transcript

00:00

Thank you We sneak Here's your shmoop news your it's

00:06

a maze ing and not at all corny Alright sorry

00:10

Sometimes we just do that Alright Moving on you know

00:13

art ignore it Don't throw up art How much slower

00:15

is inefficient Some than efficient Some in the best minimum

00:20

case for an array of n elements right here in

00:24

the rays list go all right here your potential answers

00:29

How many times slower like a rap song All right

00:35

well to answer this one we'll have to figure out

00:37

how both methods work to see exactly what would make

00:40

one of them less efficient than the other so for

00:43

efficient Some were creating a loop that begins with its

00:46

iterated at one and adds the contents of each following

00:49

array element to array in deck zero until we reach

00:51

the end In effect index zero becomes the running total

00:56

As we travel through the array makes sense and it's

00:59

pretty efficient just like the name says inefficient Some creates

01:03

a separate variable toe hold are running total then visits

01:06

each element of the array as we had done before

01:09

but here's the univision part while the value of the

01:12

current array element is greater than zero It subtract one

01:16

from it and adds one to the some variable Then

01:19

it checks it again and again and again And i

01:20

will keep doing this until the array element here is

01:23

zero So often injure in the array Had a value

01:27

of say fifty We'd have to complete this process fifty

01:29

times If an imager were a million six hundred four

01:32

thousand two hundred ninety three Well yeah inefficient is the

01:35

right word for it The difference is a bit like

01:37

someone opening a can of corn and eating each nibble

01:40

it one by one versus more standard practise of opening

01:42

the can and chugging the entire thing right there in

01:45

a sec It's the new mcdonald's product It's really cool

01:48

and fried Okay from this we can tell that the

01:51

larger the values aaron the array the larger the kansas

01:54

corn would be and the longer inefficient some would take

01:57

But this question is asking for the best case scenario

02:00

And by far the best cases faras inefficient Some is

02:02

concerned would be in a ray full of zeros It

02:04

could be enormous Hundreds of thousands of zeros and we'd

02:08

zip right through it Practically the same speed as efficient

02:10

son because we'd be avoiding that tedious wild loop entirely

02:14

The result in that best all zero case is that

02:17

bullet methods would run at the same speed or at

02:20

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

Related Videos

AP Computer Science 1.2 GridWorld Case Study and APIs
493 Views

AP Computer Science 1.2 GridWorld Case Study and APIs. What is the direction of the actor?

AP Computer Science 1.4 Standard Algorithms
200 Views

AP Computer Science 1.4 Standard Algorithms. How many times will mystery be called for mystery(n) for n > 1?

AP Computer Science 2.3 Classes and Objects
191 Views

AP Computer Science 2.3 Classes and Objects. Which of the following is correct implementation of the Country class?

AP Computer Science 3.4 Inheritance, Abstraction, and Polymorphism
204 Views

AP Computer Science 3.4 Inheritance, Abstraction, and Polymorphism. Which of the following will satisfy the conditional if statement for boo, str,...

AP Computer Science 4.2 Standard Algorithms
191 Views

AP Computer Science 4.2 Standard Algorithms. What kind of algorithm is the following?