Big O Notation: A Few Examples
Рет қаралды 193,647
8 жыл бұрынThis video is about Big O Notation: A Few Examples
Time complexity is commonly estimated by counting the number of elementary operations (elementary operation = an operation that takes a fixed amount of time to preform) performed in the algorithm.
Time complexity is classified by the nature of the function T(n). O represents the function, and (n) represents the number of elements to be acted on.
Worst-case time complexity, the longest it could possibly take with any valid input, is the most common way to express time complexity. When you discuss Big-O notation, that is generally referring to the worst case scenario. For example, if we have to search two lists for common entries, we will calculate as if both entries would be at the very end of each list, just to be safe that we don't underestimate how long it could take.
O(1) - determining if a number is odd or even. O(1) is a static amount of time, the same no matter how much information is there or how many users there are.
O(log N) - finding a word in the dictionary (using binary search). Binary search is an example of a type of "divide and conquor" algorithm.
O(N) - reading a book
O(N log N) - sorting a deck of playing cards (using merge sort)
O(N^2) - checking if you have everything on your shopping list in your cart
O(infinity) - tossing a coin until it lands on heads
As a rule of thumb, anything with N^2 or any other exponent is NOT a good algorithm for a site with multiple users. If your algorithm slows down exponentially with the input, you're going to want to look for a more efficient way to solve that problem.
Whenever you’re coding loops within loops, you want to be especially mindful of time complexity.
bigocheatsheet.com/
Big O Cheat Sheet is the place to look once you can classify your algorithm, like as a "merge-sort" or a "quick-sort".
www.coursera.org/course/algs4...
Princeton Coursera course is NOT for the faint of heart. With examples and practice in Java, this course will cover iterating over data specifically with Java, sorting, and searching algorithms.
@jenrim 7 жыл бұрын
O(N^2) is NOT exponential, O(2^n) is exponential, there's a big difference.
@phoneix24886 7 жыл бұрын
Did u also notice.. "merge search"?
@sighmon5640 7 жыл бұрын
O(N^) is quadratic (because you didnt say)
@cesarjom 6 жыл бұрын
yep, N^2 is order 2, N^3 is order 3, and so on...
@karmeshpatel4770 6 жыл бұрын
isn't O(2^n) when 2 recursive calls are made?
@fouadboukredine5808 5 жыл бұрын
O(2^n) is indeed exponential because as x grows, 2^n will grow exponentially with greater values. O(n^2) is not exponential, but there are special cases where O(n^2) grows kind of exponentially, where the chart looks close enough to be considered exponential.
@LucyRockprincess 8 жыл бұрын
Great analogies. Thank you.
@digitalconsciousness 8 жыл бұрын
I liked that all of the notations were listed out from best to worst. I didn't really understand what log n meant for the longest time, so I had no idea if n^2 was better or worse than log n for instance. This makes it a lot clearer.
@fluets5658 8 жыл бұрын
Log means the opposite of a power. So assuming that log base two of N was used here (the opposite of N^2), it would be working out 'to what power must 2 be to equal N'.For example, Log(2) would be 1 since N = 2 and 2 to the power of 1 is 2.Log(4) = 2 since 2^2 is 4.As you can see, this can make values much smaller, so it's very good. :)
@nellmv9551 7 жыл бұрын
You are good!
@SamvitAgarwal 6 жыл бұрын
What if you were to implement an algorithm that iterates through a list multiple times? Although 1 iteration is O(n) time, would multiple iterations be exponential? (Every time you iterate, the size decreases by one)
@PHLYLM 8 жыл бұрын
how can you tell if an algorithm is tight? whenever an algorithm is of complexity theta, doesnt that already imply it is tight? for example, if an algorihtm is of upper-bound n and lower bounds nlogn...;.
@nickfeldman2996 4 жыл бұрын
Thank you for the help in understanding the meanings!
@pbanikk 5 жыл бұрын
Beautiful!!
@insomiaticewok7336 7 жыл бұрын
Now I can Ace my exam, thank you!!
@ShubhamSingh-ku5ux 5 жыл бұрын
I love your teaching!!
@Ameenah1 7 жыл бұрын
Thank you so much
@abirwww 7 жыл бұрын
very helpful for computer science
@nands4410 7 жыл бұрын
This Is wrong in So many ways. 1)Divide and Conquer Cannot be branded as O(logn) e.g Merge Sort is Divide and Conquer that takes O(nlogn) and Quick Sort takes O(nlogn) in average and may go upto O(n^2) in worst case if the pivot is not randomised. 2)Merge Search Wtf? 3)An algorithm is said to be exponential time, if T(n) is upper bounded by 2^poly(n), where poly(n) is some polynomial in n. More formally, an algorithm is exponential time if T(n) is bounded by O(2^nk) for some constant k.
@JigarPatel28 6 жыл бұрын
Yo binary search is divide conquer. Check your facts. If you don't believe check this course from University of California: www.coursera.org/lecture/algorithmic-toolbox/binary-search-TTWqe
@talhaamjad_ 7 жыл бұрын
Thanks
@Thunderwolf666 8 жыл бұрын
O(n^2) isn't exponential, it's polynomial. O(2^n) would be exponential. Good explanations though.
@alimeree4299 7 жыл бұрын
You are completely right . I agree with you.
@sighmon5640 7 жыл бұрын
its quadratic, any bigger of exponent to N would probably polynomial, though
@Thunderwolf666 7 жыл бұрын
Quadratic functions ARE polynomial functions. It's Polynomial.
@sighmon5640 7 жыл бұрын
true, i was just referring to the fact that generally, when the degree is 2 in a function, they are referred as specifically quadratic. you are right though, either way
@Thunderwolf666 7 жыл бұрын
But also generally in Big O notation we're less interested in the specifics of indices and more in the type of function. But hey, we're both correct so who cares?
@bytler4518 7 жыл бұрын
Thanks freecodecamp :)! Helped me
@Reedemedknight 7 жыл бұрын
Maybe I'm confused, but isn't merge search just n and then the actual merge is logn? Help me if I'm mistaken, I'm still trying to grasp this.
@ffatheranderson 5 жыл бұрын
Mere search does (there is merge SORT not SEARCH) not exist and O(n^2) is not exponential it is quadratic(O(2^n) is exponential).
@TomGeogecko 7 жыл бұрын
This just scratches the surface, but its a start I guess.
@campermortey 8 жыл бұрын
I tried the coursera algorithm course and got completely lost after the first week. I had to pause the video every 15 seconds or so and write down what the professor was doing. Way too difficult for me
@nabiltech1366 3 жыл бұрын
Same bro.Maybe that method is not suitables for you.U can still try any methods.
@shepherdyannis697 8 жыл бұрын
I like the audio effect
@ShubhamSingh-ku5ux 5 жыл бұрын
U are fabulous 😊😊
@engkortheng 6 жыл бұрын
she just made me more confused, so how is merge sort n log n and binary search logn, is this because for sorting we sort the elements and searching we are just picking an element?hmm so confused....
@SarbbottamBandyopadhyay 8 жыл бұрын
Interesting classification. Did you mean merge sort instead of merge search?
@wtfPlatypus 8 жыл бұрын
No one give this guy advice we don't need him taking our jobs.
@MrBrb96 8 жыл бұрын
chill
@Bashir000 8 жыл бұрын
+wtfPlaypus Loser
@wtfPlatypus 8 жыл бұрын
***** Enjoy your cholera
@colonelbagshot6593 8 жыл бұрын
HERE COMES THE H1B's RUN!
@ricj9594 3 жыл бұрын
what a beautiful and intelligent woman!! congratulations
@esmailiyou 6 жыл бұрын
The board half a meter to the right with less light from the left would have made the presentation better
@pedrodfg 7 жыл бұрын
Wth.. O(N^2) is not exponencial! It has a quadratic complexity NOT exponencial. However O(2^N) is exponencial....
@fouadboukredine5808 5 жыл бұрын
Both are exponential. check with actual real numbers examples in a graph, draw a line on the graph on both, and you'll see they both are indeed exponential. O(n^2) is a little bit more exponential than O(2^n) but they are both exponential though.
@cesarjom 6 жыл бұрын
when you hear "you don't have to understand it completely" you know it's time to bail on this video
@freecodecamp 6 жыл бұрын
Everyone learns incrementally and not everyone needs to know everything.
@orkhanahmadov9963 4 жыл бұрын
FreeCodeCamp i love you guys
@II_xD_II 4 жыл бұрын
O(n^2) is quadratic, not exponential O(b^n) is exponential where b
@howtouse7189 3 жыл бұрын
can anyone solve this Q? Q.) List the complexity of following algorithms using BIG-O notation. (i) Merge Sort (ii) Quick Sort (iii) Bubble Sort (iv) Linear Search (v) Binary Search (vi) Push Operation (vii) Pop Operation (viii) Stack Traversal
@harshg2003 8 жыл бұрын
I was expecting some problems with functions as well
@lama2932 8 жыл бұрын
+Harsh Gupta problems what
@harshg2003 8 жыл бұрын
+Maati Grouni I mean some examples for e.g Prove that running time T(n) = n3(read as n cube) + 20n is Ω(n2(read as n square))
@AbhimanyuAryan 8 жыл бұрын
go to geeksforgeeks
@thegorillaz4759 4 жыл бұрын
i m subscribing this channel because of this chick not for the topics and stuff she delivers.
@ayandeedits 4 жыл бұрын
shame on u
@AshishYadav-hv9py 3 жыл бұрын
i can not concentrate on board
@logomoniclearning6680 6 жыл бұрын
Youre blocking the board hun.
@fog1257 11 ай бұрын
Exponential? Don't think so.
@mk17173n 4 жыл бұрын
she is beautiful and smart.
@ShubhamSingh-ku5ux 5 жыл бұрын
Can I know your name?
@arm9180 4 жыл бұрын
Lol. Pervert Alert
@drakZes 6 жыл бұрын
I came here looking for the explanation of the log time complexity, but she just talks about it. Bad video.
@memorablename5187 8 жыл бұрын
no offense but, unless you give code examples this is utterly useless. I have been studying this for 30mins and i could give a better explanation
@memorablename5187 8 жыл бұрын
wtfPlatypus debatable
@wtfPlatypus 8 жыл бұрын
IM RAYMOND BRADBERRY
@memorablename5187 8 жыл бұрын
wtfPlatypus SLAMMIN'
@wtfPlatypus 8 жыл бұрын
Raymond Berry How about we get some Sodie Pops?
@memorablename5187 8 жыл бұрын
wtfPlatypus i don't drink soda pop
@priyanshubansal6776 3 жыл бұрын
she is really gorgeous
@SickFlipFingrboardin 5 жыл бұрын
i couldnt learn anything because i thought about motorboating you the whole time.
@govindmishra910 6 жыл бұрын
She is cute.... okay let her teach anything...hhaha
@gatedscs 7 жыл бұрын
Good that English is your first language or else your video would be a laughing stock. Exponential and polynomial ain't no same (hohohohohoho)
@hamadnasser9676 6 жыл бұрын
You already have a big o in your chest 👀
Trouble- Free
Рет қаралды 43 М.
Back To Back SWE
Рет қаралды 167 М.
Gate Smashers
Рет қаралды 1,9 МЛН