Asymptotic Notation CS50 English Yiddish

Asymptotic NotationYouTube↗ IA↗(long shot)
Education 198.1K views 0 likes 0 dislikes 13 Jan 2013

CS50 2.4M subscribers United States YouTube↗

Click to Play Video

You've probably heard people talk about a fast or efficient algorithm

[Powered by Google Translate] איר ווע מיסטאָמע געהערט מענטשן רעדן וועגן אַ פעסט אָדער עפעקטיוו אַלגערידאַם

for executing your particular task,

פֿאַר עקסאַקיוטינג דיין באַזונדער אַרבעט,

but what exactly does it mean for an algorithm to be fast or efficient?

אָבער וואָס פּונקט טוט עס מיינען פֿאַר אַ אַלגערידאַם צו זייַן פעסט אָדער עפעקטיוו?

Well, it's not talking about a measurement in real time,

נו, עס ס ניט גערעדט וועגן אַ מעאַסורעמענט אין פאַקטיש צייַט,

like seconds or minutes.

ווי סעקונדעס אָדער מינוט.

This is because computer hardware

דאס איז ווייַל קאָמפּיוטער ייַזנוואַרג

and software vary drastically.

און ווייכווארג בייַטן דראַסטיקלי.

My program might run slower than yours,

מייַן פּראָגראַם זאל לויפן סלאָוער ווי דייַן,

because I'm running it on an older computer,

ווייַל איך בין פליסנדיק עס אויף אַ עלטערע קאָמפּיוטער,

or because I happen to be playing an online video game

אָדער ווייַל איך פּאַסירן צו זייַן פּלייינג אַן אָנליין ווידעא שפּיל

at the same time, which is hogging all my memory,

אין דער זעלביקער צייַט, וואָס איז כאָגינג אַלע מיין זכּרון,

or I might be running my program through different software

אָדער איך זאל זייַן פליסנדיק מיין פּראָגראַם דורך פאַרשידענע ווייכווארג

which communicates with the machine differently at a low level.

וואָס קאַמיוניקייץ מיט די מאַשין דיפערענטלי בייַ אַ נידעריק מדרגה.

It's like comparing apples and oranges.

עס ס ווי קאַמפּערינג apples און אָראַנדזשאַז.

Just because my slower computer takes longer

נאָר ווייַל מיין סלאָוער קאָמפּיוטער נעמט מער

than yours to give back an answer

ווי דייַן צו געבן צוריק אַן ענטפֿערן

doesn't mean you have the more efficient algorithm.

טוט נישט מיינען איר האָבן די מער עפעקטיוו אַלגערידאַם.

>> So, since we can't directly compare the runtimes of programs

>> אַזוי, זינט מיר קענען ניט גלייַך פאַרגלייַכן די רונטימעס פון מגילה

in seconds or minutes,

אין סעקונדעס אָדער מינוט,

how do we compare 2 different algorithms

ווי טאָן מיר פאַרגלייַכן 2 פאַרשידענע אַלגערידאַמז

regardless of their hardware or software environment?

ראַגאַרדלאַס פון זייער ייַזנוואַרג אָדער ווייכווארג סוויווע?

To create a more uniform way of measuring algorithmic efficiency,

צו שאַפֿן אַ מער מונדיר וועג פון מעסטן אַלגאָריטהמיק עפעקטיווקייַט,

computer scientists and mathematicians have devised

קאָמפּיוטער סיינטיס און מאַטאַמאַטישאַנז האָבן דיווייזד

concepts for measuring the asymptotic complexity of a program

קאַנסעפּס פֿאַר מעסטן די אַסימפּטאָטיק קאַמפּלעקסיטי פון אַ פּראָגראַם

and a notation called 'Big Ohnotation'

און אַ נאָוטיישאַן גערופן 'גרויס אָהנאָטאַטיאָן'

for describing this.

פֿאַר דיסקרייבינג דעם.

The formal definition is that a function f(x)

די פאָרמאַל דעפֿיניציע איז אַז אַ פֿונקציע F (X)

runs on the order of g(x)

לויפט אויף די סדר פון ג (X)

if there exists some (x) value, x₀ and

אויב עס יגזיסץ עטלעכע (X) ווערט, X ₀ און

some constant, C, for which

עטלעכע קעסיידערדיק, C, פֿאַר וואָס

f(x) is less than or equal to

F (X) איז ווייניקער ווי אָדער גלייַך צו

that constant times g(x)

אַז קעסיידערדיק מאל ג (X)

for all x greater than x₀.

פֿאַר אַלע X גרעסער ווי X ₀.

>> But don't be scared away by the formal definition.

>> אבער טאָן נישט זייַן דערשראָקן אַוועק דורך די פאָרמאַל דעפֿיניציע.

What does this actually mean in less theoretical terms?

וואָס טוט דאָס פאקטיש מיינען אין ווייניקער טעאָרעטיש תּנאָים?

Well, it's basically a way of analyzing

נו, עס ס בייסיקלי אַ וועג פון אַנאַלייזינג

how fast a program's runtime grows asymptotically.

ווי שנעל אַ פּראָגראַם 'ס רונטימע וואקסט אַסימפּטאָטיקאַללי.

That is, as the size of your inputs increases towards infinity,

וואָס איז, ווי די גרייס פון דיין ינפּוץ ינקריסיז צו ינפיניטי,

say, you're sorting an array of size 1000 compared to an array of size 10.

זאָגן, איר ניטאָ סאָרטינג אַ מענגע פון גרייס 1000 קאַמפּערד צו אַ מענגע פון גרייס 10.

How does the runtime of your program grow?

ווי טוט די רונטימע פון דיין פּראָגראַם וואַקסן?

For example, imagine counting the number of characters

פֿאַר בייַשפּיל, ימאַדזשאַן קאַונטינג די נומער פון אותיות

in a string the simplest way

אין אַ שטריקל די סימפּלאַסט וועג

by walking through the whole string

דורך גיין דורך די גאנצע שטריקל

letter-by-letter and adding 1 to a counter for each character.

בריוו-דורך-בריוו און אַדינג 1 צו אַ קאָונטער פֿאַר יעדער כאַראַקטער.

This algorithm is said to run in linear time

דאס אַלגערידאַם איז געזאגט צו לויפן אין לינעאַר צייַט

with respect to the number of characters,

מיט רעספּעקט צו די נומער פון אותיות,

'n' in the string.

'N' אין די שטריקל.

In short, it runs in O(n).

אין קורץ, עס לויפט אין אָ (N).

פארוואס איז דאָס?

Well, using this approach, the time required

נו, ניצן דעם צוגאַנג, די צייַט פארלאנגט

to traverse the entire string

צו דורך די גאנצע שטריקל

is proportional to the number of characters.

איז פּראַפּאָרשאַנאַל צו די נומער פון אותיות.

Counting the number of characters in a 20-character string

קאַונטינג די נומער פון אותיות אין אַ 20-כאַראַקטער שטריקל

is going to take twice as long as it takes

איז געגאנגען צו נעמען צוויי מאָל ווי לאַנג ווי עס נעמט

to count the characters in a 10-character string,

צו ציילן די אותיות אין אַ 10-כאַראַקטער שטריקל,

because you have to look at all the characters

ווייַל איר האָבן צו קוקן אין אַלע די אותיות

and each character takes the same amount of time to look at.

און יעדער כאַראַקטער נעמט די זעלבע סומע פון צייַט צו קוקן בייַ.

As you increase the number of characters,

ווי איר פאַרגרעסערן די נומער פון אותיות,

the runtime will increase linearly with the input length.

די רונטימע וועט פאַרגרעסערן ליניערלי מיט די אַרייַנשרייַב לענג.

>> Now, imagine if you decide that linear time,

>> איצט, ימאַדזשאַן אויב איר באַשליסן אַז לינעאַר צייַט,

O(n), just wasn't fast enough for you?

אָ (N), נאָר איז געווען ניט שנעל גענוג פֿאַר איר?

Maybe you're storing huge strings,

אפֿשר איר ניטאָ סטאָרינג ריזיק סטרינגס,

and you can't afford the extra time it would take

און איר קענען נישט פאַרגינענ די עקסטרע מאָל עס וואָלט נעמען

to traverse all of their characters counting one-by-one.

צו דורך אַלע פון זייער אותיות קאַונטינג איינער-דורך-איינער.

So, you decide to try something different.

אַזוי, איר באַשליסן צו פּרובירן עפּעס אַנדערש.

What if you would happen to already store the number of characters

וואָס אויב איר וואָלט פּאַסירן צו שוין קראָם די נומער פון אותיות

in the string, say, in a variable called 'len,'

אין דעם שטריקל, זאָגן, אין אַ בייַטעוודיק גערופן 'לען,'

early on in the program,

פרי אויף אין די פּראָגראַם,

before you even stored the very first character in your string?

איידער איר אַפֿילו סטאָרד די זייער ערשטער כאַראַקטער אין דיין שטריקל?

Then, all you'd have to do now to find out the string length,

דערנאך, אַלע איר 'ד האָבן צו טאָן איצט צו געפֿינען אויס די שטריקל לענג,

is check what the value of the variable is.

איז טשעק וואָס די ווערט פון די בייַטעוודיק איז.

You wouldn't have to look at the string itself at all,

איר וואָלט ניט האָבן צו קוקן בייַ די שטריקל זיך בייַ אַלע,

and accessing the value of a variable like len is considered

און אַקסעסינג די ווערט פון אַ בייַטעוודיק ווי לען איז געהאלטן

an asymptotically constant time operation,

אַ אַסימפּטאָטיקאַללי קעסיידערדיק צייַט אָפּעראַציע,

אָדער אָ (1).

Why is this? Well, remember what asymptotic complexity means.

פארוואס איז דאָס? נו, געדענקען וואָס אַסימפּטאָטיק קאַמפּלעקסיטי מיטל.

How does the runtime change as the size

ווי טוט די רונטימע טוישן ווי די גרייס

of your inputs grows?

פון דיין ינפּוץ וואקסט?

>> Say you were trying to get the number of characters in a bigger string.

>> זאָגן איר זענען טריינג צו באַקומען די נומער פון אותיות אין אַ ביגער שטריקל.

Well, it wouldn't matter how big you make the string,

נו, עס וואָלט נישט ענין ווי גרויס איר מאַכן דעם שטריקל,

even a million characters long,

אַפֿילו אַ מיליאָן אותיות לאַנג,

all you'd have to do to find the string's length with this approach,

אַלע איר 'ד האָבן צו טאָן צו געפֿינען די שטריקל ס לענג מיט דעם צוגאַנג,

is to read out the value of the variable len,

איז צו לייענען אויס די ווערט פון די בייַטעוודיק לען,

which you already made.

וואָס איר שוין געמאכט.

The input length, that is, the length of the string you're trying to find,

די אַרייַנשרייַב לענג, וואָס איז, די לענג פון די שטריקל איר ניטאָ טריינג צו געפֿינען,

doesn't affect at all how fast your program runs.

טוט ניט ווירקן אין אַלע ווי שנעל דיין פּראָגראַם לויפט.

This part of your program would run equally fast on a one-character string

דעם טייל פון אייער פּראָגראַם וואָלט לויפן גלייַך פעסט אויף אַ איין-כאַראַקטער שטריקל

and a thousand-character string,

און אַ טויזנט-כאַראַקטער שטריקל,

and that's why this program would be referred to as running in constant time

און אַז ס וואָס דעם פּראָגראַם וואָלט זייַן ריפערד צו ווי פליסנדיק אין קעסיידערדיק צייַט

with respect to the input size.

מיט רעספּעקט צו די אַרייַנשרייַב גרייס.

>> Of course, there's a drawback.

>> פון קורס, דאָרט ס אַ שטערונג.

You spend extra memory space on your computer

איר פאַרברענגען עקסטרע זכּרון פּלאַץ אויף דיין קאָמפּיוטער

storing the variable

סטאָרינג די בייַטעוודיק

and the extra time it takes you

און די עקסטרע צייַט עס נעמט איר

to do the actual storage of the variable,

צו טאָן די פאַקטיש סטאָרידזש פון די בייַטעוודיק,

but the point still stands,

אָבער די פונט נאָך שטייט,

finding out how long your string was

געפונען אויס ווי לאַנג דיין שטריקל איז געווען

doesn't depend on the length of the string at all.

טוט ניט אָפענגען אויף די לענג פון די שטריקל בייַ אַלע.

So, it runs in O(1) or constant time.

אַזוי, עס לויפט אין אָ (1) אָדער קעסיידערדיק צייַט.

This certainly doesn't have to mean

דאס זיכער טוט ניט האָבן צו מיינען

that your code runs in 1 step,

אַז דיין קאָד לויפט אין 1 שריט,

but no matter how many steps it is,

אָבער קיין ענין ווי פילע טריט עס איז,

if it doesn't change with the size of the inputs,

אויב עס טוט נישט טוישן מיט די גרייס פון דעם ינפּוץ,

it's still asymptotically constant which we represent as O(1).

עס ס נאָך אַסימפּטאָטיקאַללי קעסיידערדיק וואָס מיר פאָרשטעלן ווי אָ (1).

>> As you can probably guess,

>> ווי איר קענען מיסטאָמע טרעפן,

there are many different big O runtimes to measure algorithms with.

עס זענען פילע פאַרשידענע גרויס אָ רונטימעס צו מאָס אַלגערידאַמז מיט.

O(n)² algorithms are asymptotically slower than O(n) algorithms.

אָ (N) ² אַלגערידאַמז זענען אַסימפּטאָטיקאַללי סלאָוער ווי אָ (N) אַלגערידאַמז.

That is, as the number of elements (n) grows,

וואָס איז, ווי די נומער פון עלעמענטן (N) וואקסט,

eventually O(n)² algorithms will take more time

יווענטשאַוואַלי אָ (N) ² אַלגערידאַמז וועט נעמען מער צייַט

than O(n) algorithms to run.

ווי אָ (N) אַלגערידאַמז צו לויפן.

This doesn't mean O(n) algorithms always run faster

דאס טוט נישט מיינען אָ (N) אַלגערידאַמז שטענדיק לויפן פאַסטער

than O(n)² algorithms, even in the same environment,

ווי אָ (N) ² אַלגערידאַמז, אַפֿילו אין דער זעלביקער סוויווע,

on the same hardware.

אויף דער זעלביקער ייַזנוואַרג.

Maybe for small input sizes,

אפֿשר פֿאַר קליין אַרייַנשרייַב סיזעס,

the O(n)² algorithm might actually work faster,

דער אָ (N) ² אַלגערידאַם זאל פאקטיש אַרבעט פאַסטער,

but, eventually, as the input size increases

אָבער, יווענטשאַוואַלי, ווי די אַרייַנשרייַב גרייס ינקריסיז

towards infinity, the O(n)² algorithm's runtime

צו ינפיניטי, די אָ (N) ² אַלגערידאַם ס רונטימע

will eventually eclipse the runtime of the O(n) algorithm.

וועט יווענטשאַוואַלי אַקליפּס די רונטימע פון די אָ (N) אַלגערידאַם.

Just like any quadratic mathematical function

פּונקט ווי קיין קוואַדראַטיק מאַטאַמאַטיקאַל פֿונקציע

will eventually overtake any linear function,

וועט יווענטשאַוואַלי יבעריאָגן קיין לינעאַר פונקציאָנירן,

no matter how much of a head start the linear function starts off with.

קיין ענין ווי פיל פון אַ קאָפּ אָנהייב די לינעאַר פונקציאָנירן סטאַרץ אַוועק מיט.

If you're working with large amounts of data,

אויב איר ניטאָ ארבעטן מיט גרויס אַמאַונץ פון דאַטן,

algorithms that run in O(n)² time can really end up slowing down your program,

אַלגערידאַמז וואָס לויפן אין אָ (N) ² צייַט קענען טאַקע סוף אַרויף סלאָוינג אַראָפּ דיין פּראָגראַם,

but for small input sizes,

אָבער פֿאַר קליין אַרייַנשרייַב סיזעס,

you probably won't even notice.

איר מיסטאָמע וועט נישט אַפֿילו באַמערקן.

>> Another asymptotic complexity is,

>> אן אנדער אַסימפּטאָטיק קאַמפּלעקסיטי איז,

logarithmic time, O(log n).

לאַגערידמיק צייַט, אָ (קלאָץ N).

An example of an algorithm that runs this quickly

אַ בייַשפּיל פון אַ אַלגערידאַם וואָס לויפט דעם געשווינד

is the classic binary search algorithm,

איז דער קלאַסיש ביינערי זוכן אַלגערידאַם,

for finding an element in an already-sorted list of elements.

פֿאַר געפונען אַן עלעמענט אין אַ שוין-אויסגעשטעלט רשימה פון עלעמענטן.

>> If you don't know what binary search does,

>> אויב איר טאָן ניט וויסן וואָס ביינערי זוכן טוט,

I'll explain it for you really quickly.

איך וועט דערקלערן עס פֿאַר איר טאַקע געשווינד.

Let's say you're looking for the number 3

זאל ס זאָגן איר ניטאָ קוקן פֿאַר די נומער 3

in this array of integers.

אין דעם מענגע פון ינטאַדזשערז.

It looks at the middle element of the array

עס קוקט אין די מיטל עלעמענט פון דער מענגע

and asks, "Is the element I want greater than, equal to, or less than this?"

און פרעגט, "איז דער עלעמענט איך וועלן גרעסער ווי, גלייַך צו, אָדער ווייניקער ווי דעם?"

If it's equal, then great. You found the element, and you're done.

אויב עס ס גלייַך, דעמאָלט גרויס. איר געפונען דעם עלעמענט, און איר ניטאָ געטאן.

If it's greater, then you know the element

אויב עס ס גרעסער, דעמאָלט איר וויסן דעם עלעמענט

has to be in the right side of the array,

האט צו זייַן אין די רעכט זייַט פון די מענגע,

and you can only look at that in the future,

און איר קענען נאָר קוק אין אַז אין די צוקונפֿט,

and if it's smaller, then you know it has to be in the left side.

און אויב עס ס קלענערער, דעמאָלט איר וויסן עס האט צו זייַן אין די לינקס זייַט.

This process is then repeated with the smaller-size array

דעם פּראָצעס איז דעמאָלט ריפּיטיד מיט דער קלענערער-גרייס מענגע

until the correct element is found.

ביז די ריכטיק עלעמענט איז געפונען.

>> This powerful algorithm cuts the array size in half with each operation.

>> דאס שטאַרק אַלגערידאַם קאַץ די מענגע גרייס אין העלפט מיט יעדער אָפּעראַציע.

So, to find an element in a sorted array of size 8,

אַזוי, צו געפֿינען אַן עלעמענט אין אַ אויסגעשטעלט מענגע פון נומער 8,

at most (log₂8),

בייַ רובֿ (קלאָץ ₂ 8),

or 3 of these operations,

אָדער 3 פון די אַפּעריישאַנז,

checking the middle element, then cutting the array in half will be required,

קאָנטראָלירונג די מיטל עלעמענט, דעמאָלט קאַטינג די מענגע אין האַלב וועט זייַן פארלאנגט,

whereas an array of size 16 takes (log₂16),

וועראַז אַ מענגע פון גרייס 16 נעמט (קלאָץ ₂ 16),

or 4 operations.

אָדער 4 אַפּעריישאַנז.

That's only 1 more operation for a doubled-size array.

אַז ס בלויז 1 מער אָפּעראַציע פֿאַר אַ דאַבאַלד-גרייס מענגע.

Doubling the size of the array

דאַבלינג די גרייס פון דעם מענגע

increases the runtime by only 1 chunk of this code.

ינקריסיז די רונטימע דורך בלויז 1 פּייַדע פון דעם קאָד.

Again, checking the middle element of the list, then splitting.

ווידער, קאָנטראָלירונג די מיטל עלעמענט פון דער רשימה, דעמאָלט ספּליטינג.

So, it's said to operate in logarithmic time,

אַזוי, עס ס 'האט צו אַרבעטן אין לאַגערידמיק צייַט,

אָ (קלאָץ N).

But wait, you say,

אבער וואַרטן, איר זאָגן,

doesn't this depend on where in the list the element you're looking for is?

טוט ניט דעם אָפענגען אויף ווו אין די רשימה די עלעמענט איר ניטאָ קוקן פֿאַר איז?

What if the first element you look at happens to be the right one?

וואָס אויב דער ערשטער עלעמענט איר קוק בייַ כאַפּאַנז צו זייַן די רעכט איינער?

Then, it only takes 1 operation,

דעמאָלט, עס נאָר נעמט 1 אָפּעראַציע,

no matter how big the list is.

קיין ענין ווי גרויס די רשימה איז.

>> Well, that's why computer scientists have more terms

>> נו, אַז ס וואָס קאָמפּיוטער סיינטיס האָבן מער תּנאָים

for asymptotic complexity which reflect the best-case

פֿאַר אַסימפּטאָטיק קאַמפּלעקסיטי וואָס פאַרטראַכטנ דער בעסטער-פאַל

and worst-case performances of an algorithm.

און ערגסט-פאַל פּערפאָרמאַנסיז פון אַ אַלגערידאַם.

More properly, the upper and lower bounds

מער רעכט, דער אויבערשטער און נידעריקער גווול

on the runtime.

אויף די רונטימע.

In the best case for binary search, our element is

אין דער בעסטער פאַל פֿאַר ביינערי זוכן, אונדזער עלעמענט איז

right there in the middle,

רעכט דאָרט אין דער מיטן,

and you get it in constant time,

און איר באַקומען עס אין קעסיידערדיק צייַט,

no matter how big the rest of the array is.

קיין ענין ווי גרויס די מנוחה פון די מענגע איז.

The symbol used for this is Ω.

דער סימבאָל געניצט פֿאַר דעם איז Ω.

So, this algorithm is said to run in Ω(1).

אַזוי, דעם אַלגערידאַם איז געזאגט צו לויפן אין Ω (1).

In the best case, it finds the element quickly,

אין דער בעסטער פאַל, עס געפינט די עלעמענט געשווינד,

no matter how big the array is,

קיין ענין ווי גרויס די מענגע איז,

but in the worst case,

אָבער אין די ערגסט פאַל,

it has to perform (log n) split checks

עס האט צו דורכפירן (קלאָץ N) שפּאַלטן טשעקס

of the array to find the right element.

פון די מענגע צו געפֿינען די רעכט עלעמענט.

Worst-case upper bounds are referred to with the big "O" that you already know.

ערגסט-פאַל אויבערשטער גווול זענען ריפערד צו מיט די גרויס "אָ" אַז איר שוין וויסן.

So, it's O(log n), but Ω(1).

אַזוי, עס ס אָ (קלאָץ N), אָבער Ω (1).

>> A linear search, by contrast,

>> א לינעאַר זוכן, דורך קאַנטראַסט,

in which you walk through every element of the array

אין וואָס איר גיין דורך יעדער עלעמענט פון דער מענגע

to find the one you want,

צו געפֿינען די איין איר ווילן,

is at best Ω(1).

איז בייַ בעסטער Ω (1).

Again, the first element you want.

ווידער, דער ערשטער עלעמענט איר ווילן.

So, it doesn't matter how big the array is.

אַזוי, עס טוט נישט ענין ווי גרויס די מענגע איז.

In the worst case, it's the last element in the array.

אין די ערגסט פאַל, עס ס די לעצטע עלעמענט אין דער מענגע.

So, you have to walk through all n elements in the array to find it,

אַזוי, איר האָבן צו גיין דורך אַלע N יסודות אין די מענגע צו געפֿינען עס,

like if you were looking for a 3.

ווי אויב איר זענען קוקן פֿאַר אַ 3.

So, it runs in O(n) time

אַזוי, עס לויפט אין אָ (N) צייַט

because it's proportional to the number of elements in the array.

ווייַל עס ס פּראַפּאָרשאַנאַל צו די נומער פון עלעמענטן אין דער מענגע.

>> One more symbol used is Θ.

>> איינער מער סימבאָל געניצט איז Θ.

This can be used to describe algorithms where the best and worst cases

דאס קען זייַן געניצט צו באַשרייַבן אַלגערידאַמז ווו דער בעסטער און ערגסט פאלן

זענען די זעלבע.

This is the case in the string-length algorithms we talked about earlier.

דאס איז דער פאַל אין די שטריקל-לענג אַלגערידאַמז מיר גערעדט וועגן פריער.

That is, if we store it in a variable before

וואָס איז, אויב מיר קראָם עס אין אַ בייַטעוודיק איידער

we store the string and access it later in constant time.

מיר קראָם די שטריקל און צוטריט עס שפּעטער אין קעסיידערדיק צייַט.

No matter what number

ניט קיין ענין וואָס נומער

we're storing in that variable, we'll have to look at it.

מיר רע סטאָרינג אין אַז בייַטעוודיק, מיר וועט האָבן צו קוקן בייַ אים.

The best case is, we look at it

דער בעסטער פאַל איז, מיר קוקן אין עס

and find the length of the string.

און געפֿינען די לענג פון די שטריקל.

So Ω(1) or best-case constant time.

אַזוי Ω (1) אָדער בעסטער-פאַל קעסיידערדיק צייַט.

The worst case is,

די ערגסט פאַל איז,

we look at it and find the length of the string.

מיר קוקן אין עס און געפֿינען די לענג פון די שטריקל.

So, O(1) or constant time in worst case.

אַזוי, אָ (1) אָדער קעסיידערדיק צייַט אין ערגסט פאַל.

So, since the best case and worst cases are the same,

אַזוי, זינט דער בעסטער פאַל און ערגסט פאלן זענען די זעלבע,

this can be said to run in Θ(1) time.

דעם קענען זייַן האט געזאגט צו לויפן אין Θ (1) מאָל.

>> In summary, we have good ways to reason about codes efficiency

>> אין קיצער, מיר האָבן גוט וועגן צו סיבה וועגן קאָודז עפעקטיווקייַט

without knowing anything about the real-world time they take to run,

אָן געוואוסט עפּעס וועגן די פאַקטיש-וועלט צייַט זיי נעמען צו לויפן,

which is affected by lots of outside factors,

וואָס איז אַפעקטאַד דורך גורל פון אַרויס סיבות,

including differing hardware, software,

אַרייַנגערעכנט דיפערינג ייַזנוואַרג, סאָפטווער,

or the specifics of your code.

אָדער די ספּיסיפיקס פון דיין קאָד.

Also, it allows us to reason well about what will happen

אויך, עס אַלאַוז אונדז צו סיבה געזונט וועגן וואָס וועט פּאַסירן

when the size of the inputs increases.

ווען די גרייס פון דעם ינפּוץ ינקריסיז.

>> If you're running in O(n)² algorithm,

>> אויב איר ניטאָ פליסנדיק אין אָ (N) ² אַלגערידאַם,

or worse, a O(2ⁿ) algorithm,

אָדער ערגער, אַ אָ (2 ⁿ) אַלגערידאַם,

one of the fastest growing types,

איינער פון די פאַסטאַסט גראָוינג טייפּס,

you'll really start to notice the slowdown

איר וועט טאַקע אָנהייבן צו באַמערקן די סלאָודאַון

when you start working with larger amounts of data.

ווען איר אָנהייבן ארבעטן מיט גרעסערע אַמאַונץ פון דאַטן.

>> That's asymptotic complexity. Thanks.

>> אַז ס אַסימפּטאָטיק קאַמפּלעקסיטי. דאַנק.

Similar videos:

Bubble Sort
CS50
330.8K views 0 likes 0 dislikes 26 Sep 2012100% match

Game of Thrones; Or The Pain Of Falling Out Of Love With A Story
Just Write
1.6M views 53.7K likes 4.2K dislikes 04 Sep 201769% match

选择合适的生物菌，用对方法，让植物更好的成长【付老师种植技术团队官方频道】
TeacherFu'sSoillessCultivationPlanting
1.3K views 18 likes 1 dislikes 21 Oct 202069% match

【抖音九九有点热】九九生气吃醋，韩总的道歉方式也太霸道了，荷尔蒙爆棚！
Gumai Golden Harvest Agency MCN
33K views 589 likes 16 dislikes 05 Nov 202068% match

这是CSGO这些小姐姐是干嘛的，是正经躲猫猫的吗？【冷淡熊】
cold bear
70.2K views 1.4K likes 28 dislikes 13 Dec 202068% match

【抖音子豪与栗子】爱你和双标！难道不是爱情的必备技能吗？
Gumai Golden Harvest Agency MCN
19.1K views 327 likes 6 dislikes 24 Oct 202068% match

Potential energy stored in a spring | Work and energy | Physics | Khan Academy
Khan Academy
479.3K views 850 likes 66 dislikes 15 Apr 200868% match

暗黑破坏神高清版，大菠萝送帽子，他不对劲
 Uncle_Arcade82
13.9K views 135 likes 4 dislikes 19 Oct 202068% match

【抖音九九有点热】韩总一不小心摔进九九的浴缸，暧昧气氛急速升温~
Gumai Golden Harvest Agency MCN
32.5K views 578 likes 14 dislikes 07 Nov 202068% match

【抖音顾城】小助理和顾总裁莫名其妙换了身体，接下来会发生什么？
Gumai Golden Harvest Agency MCN
169.7K views 2K likes 55 dislikes 06 Apr 202067% match

How to Clean Your Dyson | Dyson Vacuum Cleaning
LaneVids & Dad Reviews Shorts
783K views 2.3K likes 342 dislikes 27 Apr 201267% match

女兒離家多年失聯，丈母娘心疼女婿想讓他再娶，5年後女兒回來了【阿鑌視野】
Aunt's vision
6.5K views 22 likes 5 dislikes 13 Nov 202067% match

原味墨西哥包帕帕罗蒂表皮香酥的面包店热卖款面包 Rotiboy Buns
Sweet Taste Kitchen
20.3K views 491 likes 7 dislikes 15 Jan 202167% match

KESİNLİKLE OKUNMASI GEREKEN 7 KİŞİSEL GELİŞİM KİTABI
Burak Bilici
12.9K views 809 likes 15 dislikes 26 Dec 202067% match

今天是個好日子，三哥帶著兄弟姐妹們去接新娘，過程太熱鬧了
 Farmer's Three Sisters
164.6K views 2.4K likes 121 dislikes 24 Aug 202067% match

DIY Silicone Mold - Easiest and Cheapest Method Ever - Easy Silicone Mold Making
Timber Ridge Gifts
1.2M views 13.3K likes 1.5K dislikes 08 Jan 201867% match

Magic Numbers
CS50
27.8K views 82 likes 2 dislikes 07 Oct 201567% match

Lose Belly Fat I भरपेट खाना वजन घटाना I How to lose weight fast I No exercise No Diet
Health City
35K views 1.2K likes 51 dislikes 10 Jan 202166% match

【抖音会变身的九九】九九换衣服，闺蜜的男朋友故意推开门，此仇不报非君子
 Gumai Golden Harvest Agency MCN
12.8K views 237 likes 5 dislikes 11 Oct 202066% match

Prima lezione Autoipnosi
Academy of dr. MARCO PARET
2.5K views 119 likes 4 dislikes 24 Feb 202066% match

想要解殺、得先自殺2次，好久沒有看過這麼過癮的車兵搏殺了！【象棋教室】
Chess classroom
3.8K views 40 likes 2 dislikes 24 Oct 202066% match

【抖音顾城】小女孩误闯顾总裁办公室，拿出5百元要买妈妈的时间，小助理哭了
 Gumai Golden Harvest Agency MCN
315.4K views 4K likes 146 dislikes 04 May 202066% match

没带5个字的肥料都是“假肥料”，挑好肥料，记住这几点就可以【付老师种植技术团队】
TeacherFu'sSoillessCultivationPlanting
2.3K views 27 likes 0 dislikes 31 Oct 202066% match

二英蒸了一大锅萝卜肉馅包子，配上霞姐给的小蒜酱，就着吃太美了！【陕北景向龙】
Jing Xianglong in Northern Shaanxi
10K views 411 likes 11 dislikes 07 Dec 202066% match

Producer Tips | Ableton Drum LOOP Tricks - Tune Drums, Extract Grooves and Slice Samples
Sanjay C
10.4K views 668 likes 7 dislikes 02 Aug 202066% match

閨蜜從綿陽下來玩，雯雪和小羊忙得手忙腳亂，真是有點興師動眾了【90後寶媽雯雪】

4.9K views 73 likes 14 dislikes 21 Oct 202066% match

【抖音破产姐弟】姐弟俩遭遇事业重大危机，没想到竟出现转机？
Gumai Golden Harvest Agency MCN
157.1K views 2.3K likes 77 dislikes 24 Oct 202066% match

【抖音顾城】弟弟和小助理合伙，趁顾总睡觉恶整总裁，顾总裁你俩完蛋了！
Gumai Golden Harvest Agency MCN
468K views 4.3K likes 217 dislikes 13 Mar 202066% match

气死大爷专用残局！保证一局一个大爷！【四郎讲棋】
Shiro speaks chess
39.8K views 485 likes 20 dislikes 22 Dec 202066% match

電腦提示大優、可按照提示走下去又一直鬼打轉贏不到，真窩火【象棋教室】
Chess classroom
2.7K views 43 likes 1 dislikes 10 Mar 202166% match

Settings Privacy About Contact Donate