Power of Heap

[@jironymojirolamus913]

Good video, thanks. However, searching in a sorted linked list is O(n) still, as far as I understand.

[@ramkumartr1501]

A great chain of help for student community bro. Hats off ✨

[@aditya234567]

Sir nice video but I feel even sorted linked list searching takes 0(N ) time not logN 7:00

[@techdose4u]

If you can't have random access then it should. You may improve complexity if Linked List is implemented using nodepool.

[@charlesopuoro5295]

Thank you very much for this comparisons as it lends perspective.

[@kunalsoni7681]

Really very informative ❤️ video 😊😊 Thank you so much sir 💕😊

[@techdose4u]

Welcome :)

[@yhimanshu22]

your explanations are great.

[@youssefelamrani7905]

damn your way of explaining is so nice

[@techdose4u]

Thanks

[@salihedneer8975]

Sir searching in heap will only take logn right ? Since we dont need to search everything

[@techdose4u]

No, searching a random element will be linear.

[@md.mehedihasan2343]

How can you binary search on a sorted linked list? is it possible ?

[@famueduyou]

Please feel free to correct me :) Imagine you assign each of the reference in the linked list a specific index/order and create a separate out of place array for them, O(n) for both space and time. Then do binary search on that new array, and refer back to the respective node in the linked list. That's just my idea, but I can be wrong.

[@techdose4u]

directly it may not be possible but while insertion you can take extra space to save the UID_address in a sorted set to apply bounded search. If you wanna remove something then the map balances itself (self balancing BST). If you wanna add something anywhere you will have access to adjacent node and you need to get another UID_address which fits in between the adjacent keys. Ordering is taken care by self-balancing BST. Since its non-trivial and requires usage of other Data Structures, hence we limit ourself to say binary search is not directly possible but saying its not possible no matter what would be an over-statement. Hope you got it.

[@AJPUJARITHRINADHSAI]

I wonder how one can apply binary search on linked list?!

[@sharafmakk2936]

We can't, there is no possible way to guess the position of the half of linked list in memory

[@krishind99]

Great info. Much appreciated

[@badrulhussain5545]

Can you do a video on Big O?

[@techdose4u]

I already did. Please watch it in time complexity playlist.

[@syamprasadupputalla8233]

thank you

[@tonyz2203]

i love you, you made me feel like I can code

[@techdose4u]

Great ❤️

[@pddivin]

Are we able to apply BS on the linked list? We can not access it by index. I wonder how?

[@anupama1381]

Thanks

[@techdose4u]

Welcome :)

[@pottalokesh2039]

Really good sir .

[@techdose4u]

Thanks :)

[@davngo]

At 4:02 it’s incorrect. Inserting into a sorted array is O(logn) not O(N). Since it’s sorted you can use binary search to figure out where to do the insertion.

[@techdose4u]

But after insertion you need to shift all the elements on one end by 1 position :)

[@davngo]

@@techdose4u oh yes, your correct. Thank you sir.

[@techdose4u]

@@davngo no problem :)

[@JohnDoe-lf1jz]

high quality content

[@ankitverma1790]

How searching in a sorted LL can be O(logN) ? you need to find the middle node which will be O(N)

[@AJPUJARITHRINADHSAI]

exactly!

[@techdose4u]

directly it may not be possible but while insertion you can take extra space to save the UID_address in a sorted set to apply bounded search. If you wanna remove something then the map balances itself (self balancing BST). If you wanna add something anywhere you will have access to adjacent node and you need to get another UID_address which fits in between the adjacent keys. Ordering is taken care by self-balancing BST. Since its non-trivial and requires usage of other Data Structures, hence we limit ourself to say binary search is not directly possible but saying its not possible no matter what would be an over-statement. Hope you got it.

[@dharmeshupadhyay4778]

sir you are loocking awesome

[@techdose4u]

😅

[@lasbutious116]

Sir, Using a sorted linked list, finding the min and deleting min will both have O(1) complexity. Only the insertion will have 0(n) time complexity. So, there will be draw O(1) between heap n sorted linked list while finding min. deletion of min value will be faster in linked list only downside of linked list will be the insertion is it worth to use a new data structure heap just for faster insertion ?? I am new to DSA. Please help me understand it

[@panavkumar9009]

Yes it is totally worth it. Firstly because when you will be making big software then the amount of data that needs to be stored will reach in many GBs or maybe TBs also. So, any thing that would improve the time taken even if slightly must be done. Secondly, even though the time taken by Linked List appears to be same yet another big factor is the space that we need to use to form a linked list. In formation of a linked list we need an int data type and also a pointer that will store the address of the next block. So, this worsens the space complexity.

[@anonymous9217w2]

god level!

[@chaitanyamallick1949]

ty sir ,ty very much

[@supernova7870]

Sir, why searching takes O(N) time in heap , it's similar to BST there it take log(N) times to search ?

[@techdose4u]

BST has a special property of storing values. We can make decision at any node which way to search. But heap has a different property, so we need linear search.

[@supernova7870]

@@techdose4u Sir , got it. Thanks :)

[@tejashreesalvi]

Nice Videos

[@techdose4u]

Thanks

[@revarevanth1800]

For creating an array to min heap takes nlogn

[@techdose4u]

O(N) using build heap.

[@poojitharavuri2943]

Thanks sir. Till now i thought we cant apply binary search on linkedlist. Now I got to know abt skip list. I will learn it. But the time complexity is same o(n) but u have written o(log n).

[@techdose4u]

For which part are you suggesting ?

[@poojitharavuri2943]

@@techdose4u in sorted linkedlist, u said that for searching it takes o(log n). But in gfg they said it is o(n)

[@pallavirawat7128]

@@poojitharavuri2943 that is through binary search

[@hymnish_you]

Thanks Sir, I have a question.Can we apply binary search in sorted ll? 6:43

[@aashimakansal3171]

I dont think we can apply binary search in a linked list

[@hymnish_you]

@@aashimakansal3171 Yes

[@techdose4u]

Main problem for applying Binary Search is to access any element randomly in O(1). You can use skip list for searching in optimized time in LL.

[@hymnish_you]

@@techdose4u Thanks sir, I have never heard about the skip list before.

[@saiyaswanthammineni3885]

@@techdose4u but binary search on ll takes O(n) time complexity , isn't it , but ya sure skip list data structure take O(logn)

[@thinkverse94]

Hi Suriya bro, I've one doubt. Can you please clarify for me? Last 3 years I'm working as a manual and automation tester in Embedded Networking, somehow I entered into this domain, but I've been self-interested in coding & want to be a developer. but, in the developer interview, I don't have an experience of dev to show. I'm not getting interested to work on testing, my minds want to be a developer but not able to do. It's internally hurting me a lot. what to do? Need your suggestion, please.

[@techdose4u]

You should learn and do some personal projects.

[@nextgen2006]

How do u get this black background and bright colors ?

[@yipyiphooray339]

black magic

[@zr0724]

even if the linked list is sorted , it will take O(n) time to search. its the nature of linked list , you are wrong.

[@techdose4u]

directly it may not be possible but while insertion you can take extra space to save the UID_address in a sorted set to apply bounded search. If you wanna remove something then the map balances itself (self balancing BST). If you wanna add something anywhere you will have access to adjacent node and you need to get another UID_address which fits in between the adjacent keys. Ordering is taken care by self-balancing BST. Since its non-trivial and requires usage of other Data Structures, hence we limit ourself to say binary search is not directly possible but saying its not possible no matter what would be an over-statement. Hope you got it.

[@zr0724]

@@techdose4u Since you did not mentioned that we need help from some other datastructure (BST), so i was confused.

[@varshneyshuchi]

Prerequisite?

[@techdose4u]

No prerequisite for this. It's the 1st video. You will understand the entire concepts once you complete all the videos starting from the next one.

[@tushar8998]

How can you apply binary search on a sorted link list? You can't index a list. Please don't give out wrong information to students.

[@techdose4u]

directly it may not be possible but while insertion you can take extra space to save the UID_address in a sorted set to apply bounded search. If you wanna remove something then the map balances itself (self balancing BST). If you wanna add something anywhere you will have access to adjacent node and you need to get another UID_address which fits in between the adjacent keys. Ordering is taken care by self-balancing BST. Since its non-trivial and requires usage of other Data Structures, hence we limit ourself to say binary search is not directly possible but saying its not possible no matter what would be an over-statement. Hope you got it.

[@famueduyou]

1:06 Can someone pls explain how is this n+n = n, but not n*n = n^2? 1:54. Thanks in advance :)

[@DarksideRowsey]

n+n is 2n, and in big o notation we generally drop any constants and so O(2n) is the same as O(n). n*n doesn't create a constant, but instead exponentially increases complexity significantly. The difference between 2n and n is not generally significant. To clarify, if it were 2n*n we would end up with O(n^2) since we'd drop the constant. Hope that helps!

[@vigosimracing9057]

right

[@techdose4u]

:)

[@baskars1342]

Sir are you software at google

[@techdose4u]

No

[@tsunningwah3471]

Vd

[@vishnuvarma2120]

nice to see ur face for first time

[@techdose4u]

:)

[@StoryGicRohit]

The Only thing missing here is Interaction with students in between explaining

[@tsunningwah3471]

Hjbb

[@tsunningwah3471]

Bbbbbbb😂😂😂😂😂😂