Recurrence Relation - Intro to Algorithms Udacity English (auto-generated) English

Recurrence Relation - Intro to AlgorithmsYouTube↗ IA↗(long shot)
Education 6.3K views 7 likes 1 dislikes 27 Jun 2012

Udacity 651K subscribers United States YouTube↗

Click to Play Video

so what we're gonna right now is a

What we're going to do right now is a recurrence relation,

recurrence relation which is a kind of recursive mathematical function which is

which is a kind of recursive mathematical function,

a good match for this recursive algorithmic expression for a rec Russian

which is a good match for this recursive algorithmic expression for Rec<u>Russian--</u>

so rec Russian recurrence relation

Rec<u>Russian recurrence relation.</u>

looking at the structure of rec Russian if a is 0 then it's gonna execute one

Looking at the structure of Rec<u>Russian, if a is 0, then it's going to execute 1 statement--</u>

statement basically the test to see whether it's zero and then returned

basically the test to see whether it’s 0 and returns.

otherwise if a is bigger than zero and even let's take a look at what rec Russian does in that case so we come in

Otherwise, if a is bigger than 0 and even, let's take a look at what Rec<u>Russian does in that case.</u>

here with a number that is even and

We come in here with a number that is even and greater than 0 is going to execute

greater than zero it's going to execute the condition of this if statement which

the condition of this if statement, which fails so there's 1 of that.

fails so there's 1 of that then one more to do this plus it's going to recursively work out the value of this

Then 1 more to do this plus it's going to recursively workout the value of this quantity.

quantity and then one more operation to

Then one more operation to multiply that by 2.

multiply that by 2 I call it a total of 3 plus however long it takes to multiply a over 2 times B now we don't know what

I call a total of 3 plus however long it takes to multiply a over 2 times b.

that is we're imagining that we're going

We don't know what that is.

to be able to create a function T that

We're imaging that we're going be able to create a function T

is going to give us the answer to that

that is going to give us the answer to that.

so let's just leave it at that for now

Let's just leave it at that for now.

and finally in the case where a is odd it's going to execute the condition of

Finally, in the case where a is odd, it's going to execute the condition of this if statement,

this if statement the condition of this 8 if statement both of which will fail

the condition of this if statement, both of which will fail.

then it will recursively compute the product and then basically execute the

Then it will recursively compute the product, and then basically execute the returns.

return so a total of 3 statements plus however long it takes to do the

A total of 3 statements plus however long it takes to do the recursive call--

recursive call so three statements plus this particular kind of recursive call

so 3 statements plus this particular kind of recursive call.

so this now is a as a mathematical

This now is a mathematical specification of a function.

specification of a function we don't know at the moment what the relationship is between a and T of a but at least

We don't know at the moment what the relationship is between a and T(a),

it's fully specified now it turns out

but at least it's fully specified.

that you actually can solve this pretty

It turns out that you actually can solve this pretty easily

easily by using what we already worked out about the number of times you can

by using what we already worked out about the number of times

divide a number a in half rounding down

you can divide a number a in half, rounding down if it's odd,

if it's odd before you get down to zero

before you get down to 0.

see if you can put that together to try

See if you can put that together to try to answer the question

to answer the question what does T of a equal from these set of choices

what does T(a) equal from these set of choices.

Similar videos:

Halving - Intro to Algorithms
Udacity
5.9K views 3 likes 0 dislikes 27 Jun 2012100% match

Algorithms Are Cool - Intro to Algorithms
Udacity
5.4K views 12 likes 0 dislikes 27 Jun 2012100% match

Build Heap - Intro to Algorithms
Udacity
20.8K views 75 likes 4 dislikes 19 Jul 2012100% match

Making a SAT graph - Intro to Algorithms
Udacity
3.4K views 18 likes 0 dislikes 23 Feb 2015100% match

Order Statistics - Intro to Algorithms
Udacity
5.4K views 6 likes 9 dislikes 19 Jul 2012100% match

Create Graph With Eulerian Tour - Intro to Algorithms
Udacity
7.4K views 6 likes 1 dislikes 23 Feb 2015100% match

NP-Hard - Intro to Algorithms
Udacity
6.3K views 17 likes 3 dislikes 23 Feb 2015100% match

Big-Theta Examples - Intro to Algorithms
Udacity
17.9K views 80 likes 102 dislikes 29 Jun 2012100% match

Reduce SAT to 3-Colorability - Intro to Algorithms
Udacity
10.8K views 14 likes 84 dislikes 23 Feb 2015100% match

Top K Problem - Intro to Algorithms
Udacity
6.2K views 11 likes 8 dislikes 19 Jul 2012100% match

Eulerian Path - Intro to Algorithms
Udacity
5.2K views 2 likes 0 dislikes 27 Jun 2012100% match

Measuring Time - Intro to Algorithms
Udacity
7.3K views 3 likes 0 dislikes 27 Jun 2012100% match

Eulerian Path Solution - Intro to Algorithms
Udacity
15.9K views 64 likes 1 dislikes 27 Jun 2012100% match

Reduce 3-Colorability to SAT - Intro to Algorithms
Udacity
11.8K views 53 likes 8 dislikes 23 Feb 2015100% match

How Many Additions - Intro to Algorithms
Udacity
7.4K views 1 likes 0 dislikes 27 Jun 2012100% match

Steps For Naive - Intro to Algorithms
Udacity
5.7K views 1 likes 0 dislikes 27 Jun 2012100% match

Introduction - Intro to Algorithms
Udacity
35.6K views 113 likes 1 dislikes 27 Jun 2012100% match

Finding Bridge Edges - Intro to Algorithms
Udacity
7.8K views 21 likes 20 dislikes 23 Feb 2015100% match

NP-Completeness - Intro to Algorithms
Udacity
8.9K views 30 likes 9 dislikes 23 Feb 2015100% match

Longest Simple Path - Intro to Algorithms
Udacity
17.4K views 32 likes 27 dislikes 23 Feb 2015100% match

Graph Coloring is NP-Complete - Intro to Algorithms
Udacity
10.1K views 20 likes 12 dislikes 23 Feb 2015100% match

Recurrence Relation - Intro to Algorithms
Udacity
5.1K views 0 likes 31 dislikes 23 Feb 2015100% match

Lower Bound on Complexity - Intro to Algorithms
Udacity
11.9K views 21 likes 23 dislikes 23 Feb 2015100% match

Down Heapify - Intro to Algorithms
Udacity
5.1K views 10 likes 1 dislikes 19 Jul 2012100% match

Pathway That Can Use Two Nodes - Intro to Algorithms
Udacity
19.5K views 408 likes 7 dislikes 08 Aug 2012100% match

Running Time - Intro to Algorithms
Udacity
9.8K views 12 likes 1 dislikes 27 Jun 2012100% match

Code for Dijkstra - Intro to Algorithms
Udacity
9.9K views 20 likes 4 dislikes 23 Feb 2015100% match

Top K Code - Intro to Algorithms
Udacity
722 views 2 likes 0 dislikes 19 Jul 2012100% match

Matrix Multiplication - Intro to Algorithms
Udacity
6K views 8 likes 7 dislikes 23 Feb 2015100% match

Divide And Conquer - Intro to Algorithms
Udacity
35.1K views 141 likes 15 dislikes 27 Jun 2012100% match

Settings Privacy About Contact Donate