Explore
For Enterprise
Join for Free
Log In

Arts and Humanities
Business
Computer Science
Data Science
Information Technology
Health
Math and Logic
Personal Development
Physical Science and Engineering
Social Sciences
Language Learning
Degrees
Certificates

Explore all of Coursera

Browse
Search
For Enterprise
Log In
Join for Free

Computing Runtimes

Loading...

Algorithmic Toolbox

University of California San Diego

4.7 (4,959 ratings) | 160K Students Enrolled

Course 1 of 6 in the Data Structures and Algorithms Specialization

The course covers basic algorithmic techniques and ideas for computational problems arising frequently in practical applications: sorting and searching, divide and conquer, greedy algorithms, dynamic programming. We will learn a lot of theory: how to sort data and how it helps for searching; how to break a large problem into pieces and solve them recursively; when it makes sense to proceed greedily; how dynamic programming is used in genomic studies. You will practice solving computational problems, designing new algorithms, and implementing solutions efficiently (so that they run in less than a second). Do you have technical problems? Write to us: coursera@hse.ru

Skills You'll Learn

Dynamic Programming, Debugging, Software Testing, Algorithms, Computer Programming

Reviews

4.7 (4,959 ratings)

5 stars
3,696 ratings
4 stars
1,004 ratings
3 stars
176 ratings
2 stars
36 ratings
1 star
47 ratings

PR

Feb 10, 2019

The course is perfectly designed. The perfect start for those who start with data structures and algorithms. The Dynamic programming was a little bit tough but overall course is perfectly designed

AG

Feb 19, 2018

best course for clearing basics of algorithms as well as learning by doing and blow your mind by thinking hard from different prospectives to get desired solutions of programming assignments ...

From the lesson

Algorithmic Warm-up

In this module you will learn that programs based on efficient algorithms can solve the same problem billions of times faster than programs based on naïve algorithms. You will learn how to estimate the running time and memory of an algorithm without even implementing it. Armed with this knowledge, you will be able to compare various algorithms, select the most efficient ones, and finally implement them as our programming challenges!

Computing Runtimes10:04

Asymptotic Notation6:54

Big-O Notation6:58

Using Big-O10:09

Taught By

Alexander S. Kulikov
Visiting Professor
Michael Levin
Lecturer
Neil Rhodes
Adjunct Faculty
Pavel Pevzner
Professor
Daniel M Kane
Assistant Professor

Transcript

Hello everybody, welcome back to data structures and algorithms specialization.

Today, we're going to be talking about what really goes into computing runtimes

and really understanding how long it takes a program to work.

So in particular, today we're really going to dive in.

Up to this point we're using this sort of rough

number of lines of code executed count.

And today we're going to talk about how accurate this is and

what sorts of complications come in.

And in particular we'll see that if we actually want something that's sort of

fundamentally an accurate measure of runtime, it's going to be a huge mess.

We're going to have to bring in all sorts of extra data that aren't

really convenient for us.

And so, we're really sort of

talking about the problem that comes in with computing runtimes in algorithms.

Something that we're not going to resolve really until the next lecture.

So to start with, let's look at this algorithm that we had for

computing Fibonacci numbers.

Remember we created an array.

We assigned the 0th element to 0.

The first element to 1.

Then, we have this big for loop where we set the i'th element to the sum of the i

minus first and i minus second elements and

then at the end of the day we return the nth element.

So we determined that when we ran this program we executed about 2n + 2 lines

of code.

But we should really ask ourselves, is this number of lines of code executed

really sort of an accurate description of the runtime of the algorithm?

And, I mean, somehow, implicitly, this measure of lines of code

assumes that, sort of, any two lines of code are sort of comparable to each other.

They're sort of one basic operation.

And so, let's actually look at this program in some detail and

see what goes into some of these lines of code and see how valid this assumption is.

So to start with, we create this array.

And what happens when you try to initialize an array?

Well, this depends a lot on your memory management system.

Fundamentally, all you have to do is find some space in memory and

then get to pointer to the first location.

On the other hand, how exactly you find this, maybe you need to shuffle some other

things around to make room for it, maybe after you allocate the array, you then

want to zero out all of the entries so that you don't have junk sitting in there.

And so, it's not entirely clear.

It depends a little bit on how exactly your program is being interpreted.

But it could be pretty fast.

It could actually take a while, depending on circumstances.

Let's look at the next line.

This is just a simple assignment, we set the 0 entry to 0.

However, if you really look at this,

at the machine level, you're doing a bit more work, you need to load up the pointer

to the 0th element to the array, you maybe then have to do some pointer arithmetic,

you then need to store this literal 0 into that spot in memory.

It could actually be not one operation but a few operations.

Similarly when we set the first element to one,

you have to do this very similar set of things.

Next there's this for loop and with the for loop, again every time you

you have to do a few things, you need to increment the value of i.

You then need to compare i to n to see if you need to break out of the loop and

if it is, you need to branch,

you need to move to another instruction in your program after the for loop.

Next up there's this addition and here we have to do some things, we have to

look up two values in the array, we have to write to a third value in the array.

All of this involves the same sort of pointer arithmetic,

and memory lookups, and writes that we were talking about before, but

we also have to do this addition.

And if it were just a normal addition, maybe it wouldn't be such a big deal.

However, this is addition of two Fibonacci numbers, and

if you'll recall from a couple of lectures ago, we found that Fibonacci numbers were

pretty big, in fact, so big, they probably don't fit in a single machine word.

So adding two of them together actually takes a non-trivial amount of time.

So somehow, not only do you have to do all of these,

array arithmetic things but, the actual addition of the Fibonacci

numbers is actually a pretty non-trivial operation.

And then we do this return stuff where we have to do an array lookup which involves

all the sorts of things we talked about already and then have to do a return which

sort of is going to operate with the program stack and

pop it up a level and return an answer.

So in conclusion, this program has six lines of code to it but

the amount of work being done in various lines of code is very, very different.

Exactly what goes into each line of code is not sort of at all the same thing.

Maybe we want to reconsider the fact that this count,

that the number of lines of code, is sort of our runtime.

Maybe we need to measure something else.

So what else should we do?

Well, if you want to be totally correct about what we actually care about,

what you need to say is, well, we're going to take this program,

we're going to run it on some real life computer.

And we'd like to know how much actual time it will take for

this program to finish. That is fundamentally what we want to know.

Unfortunately, in order to figure that out we need to know all kinds of messy

details.

We need to know things like the speed of the computer that we're running it on.

If you run it on a big supercomputer,

it'll take a lot less time than if you run it on your cell phone.

The system architecture of the computer will matter.

Exactly what operations your CPU supports and exactly how long they take

relative to one another, those are all going to have an effect on your runtime.

The compiler being used is also going to make a difference.

In practice, what you'll do is, you'll write this program in some high-level

language, in C or Java or Python or

something, and then you'll run it through a compiler to turn it into machine code.

And then the compiler,

though, isn't just sort of doing something completely obvious.

It's performing all kinds of interesting optimizations to your code.

And which optimizations it performs, and

how they interact with exactly what you've written.

That's all going to have an impact on the final runtime.

Finally, you're going to care about details of the memory hierarchy.

If your entire computation fits into cache,

it will probably run pretty quickly.

However, if you have to start doing lookups into RAM,

things will be a lot slower.

RAM lookups actually take a fair bit of time.

If, on the other hand, you run out of memory in RAM and having to start writing

some of these memory operations to disk, things are going to go a lot slower.

Lookups to hard disk can take milliseconds which are forever in computer time.

And so, exactly how much memory is stored in these various levels of the hierarchy,

and exactly how long the lookups take, and how good the algorithms

about to predict what things you're going to look up in the future are.

Those are all going to affect your runtime.

And so, putting it all together, we found basically a problem.

Figuring out accurate runtimes is a huge mess.

You need to know all of these details and

you need to figure out how everything interacts.

And we're going to be talking about a lot of algorithms in the class.

And we're going to need to tell you about runtimes for all of them and

we don't want to have to do this huge mess

every single time we have a new algorithm that we want to analyze.

And this is an issue.

And another issue it was just that,

in practice I mean, this is all assuming that you did know these details.

In practice, you don't know a lot of these details, because you're writing a program,

it's going to be run on somebody else's computer, and

you've got no idea what their system architecture looks like on that computer,

because you don't know what the computer is.

You don't know who's running it.

In fact, there'll be several people running it on different computers with

different architectures and different speeds, and it'll be a mess.

And you really don't want to compute the runtime separately for

every different client.

So we've got a big problem here and we're not going to solve it today but

next lecture we're going to talk about how we get around this.

And what we really want is we want a new way to measure runtime that allows

us to get some reasonable answer without knowing these sorts of details.

And one of the key tricks that you should be looking at,

that we'll be using to solve this problem, is we're going to be getting things that

really give us results for very large inputs.

They tell us,

not necessarily how long it actually takes in terms of real seconds,

minutes, and hours, but tell us sort of how our runtime scales with input size.

And in practice this is a very important thing, because oftentimes,

we really do care what happens when we have huge inputs,

millions of data points that we need to analyze, how long does it take?

And so, come back next lecture,

we'll talk about how we resolve some of these issues, and talk about some very

useful notation that we will be using throughout the rest of this sequence.

So I hope you come back then, and I'll see you there.

Explore our Catalog

Join for free and get personalized recommendations, updates and offers.

Coursera provides universal access to the world’s best education, partnering with top universities and organizations to offer courses online.

© 2019 Coursera Inc. All rights reserved.

Download on the App Store

Get it on Google Play

Coursera
About
Leadership
Careers
Catalog
Certificates
MasterTrack™ Certificates
Degrees
For Enterprise
For Government

Community
Learners
Partners
Developers
Beta Testers
Translators

Connect
Blog
Facebook
LinkedIn
Twitter
Instagram
YouTube
Tech Blog

More
Terms
Privacy
Help
Accessibility
Press
Contact
Directory
Affiliates