COURSES
MBAData Science & AnalyticsDoctorate Software & Tech AI | ML MarketingManagement
Professional Certificate Programme in HR Management and AnalyticsPost Graduate Certificate in Product ManagementExecutive Post Graduate Program in Healthcare ManagementExecutive PG Programme in Human Resource ManagementMBA in International Finance (integrated with ACCA, UK)Global Master Certificate in Integrated Supply Chain ManagementAdvanced General Management ProgramManagement EssentialsLeadership and Management in New Age BusinessProduct Management Online Certificate ProgramStrategic Human Resources Leadership Cornell Certificate ProgramHuman Resources Management Certificate Program for Indian ExecutivesGlobal Professional Certificate in Effective Leadership and ManagementCSM® Certification TrainingCSPO® Certification TrainingLeading SAFe® 5.1 Training (SAFe® Agilist Certification)SAFe® 5.1 POPM CertificationSAFe® 5.1 Scrum Master Certification (SSM)Implementing SAFe® 5.1 with SPC CertificationSAFe® 5 Release Train Engineer (RTE) CertificationPMP® Certification TrainingPRINCE2® Foundation and Practitioner Certification
Law
Job Linked
Bootcamps
Study Abroad
Master of Business Administration (90 ECTS)Master of Business Administration (60 ECTS)Master in Computer Science (120 ECTS)Master in International Management (120 ECTS)Bachelor of Business Administration (180 ECTS)B.Sc. Computer Science (180 ECTS)MS in Data AnalyticsMS in Project ManagementMS in Information TechnologyMasters Degree in Data Analytics and VisualizationMasters Degree in Artificial IntelligenceMBS in Entrepreneurship and MarketingMSc in Data AnalyticsMS in Data AnalyticsMaster of Science in AccountancyMS in Computer ScienceMaster of Science in Business AnalyticsMaster of Business Administration MS in Data ScienceMS in Information TechnologyMaster of Business AdministrationMS in Applied Data ScienceMaster of Business AdministrationMS in Data AnalyticsM.Sc. Data Science (60 ECTS)Master of Business AdministrationMS in Information Technology and Administrative Management MS in Computer Science Master of Business Administration MBA General Management-90 ECTSMSc International Business ManagementMS Data Science MBA Business Technologies MBA Leading Business Transformation Master of Business Administration MSc Business Intelligence and Data ScienceMS Data Analytics MS in Management Information SystemsMSc International Business and ManagementMS Engineering ManagementMS in Machine Learning EngineeringMS in Engineering ManagementMSc Data EngineeringMSc Artificial Intelligence EngineeringMPS in InformaticsMPS in Applied Machine IntelligenceMS in Project ManagementMPS in AnalyticsMS in Project ManagementMS in Organizational LeadershipMPS in Analytics - NEU CanadaMBA with specializationMPS in Informatics - NEU Canada Master in Business AdministrationMS in Digital Marketing and MediaMS in Project ManagementMaster in Logistics and Supply Chain ManagementMSc Sustainable Tourism and Event ManagementMSc in Circular Economy and Sustainable InnovationMSc in Impact Finance and Fintech ManagementMS Computer ScienceMS in Applied StatisticsMS in Computer Information SystemsMBA in Technology, Innovation and EntrepreneurshipMSc Data Science with Work PlacementMSc Global Business Management with Work Placement MBA with Work PlacementMS in Robotics and Autonomous SystemsMS in Civil EngineeringMS in Internet of ThingsMSc International Logistics and Supply Chain ManagementMBA- Business InformaticsMSc International ManagementMS Computer Science with AIML ConcentrationMBA in Strategic Data Driven ManagementMaster of Business AdministrationMSc Digital MarketingMBA Business and MarketingMaster of Business AdministrationMSc Digital MarketingMSc in Sustainable Luxury and Creative IndustriesMSc in Sustainable Global Supply Chain ManagementMSc in International Corporate FinanceMSc Digital Business Analytics MSc in International HospitalityMSc Luxury and Innovation ManagementMaster of Business Administration-International Business ManagementMS in Computer EngineeringMS in Industrial and Systems EngineeringMSc International Business ManagementMaster in ManagementMSc MarketingMSc Business ManagementMSc Global Supply Chain ManagementMS in Information Systems and Technology with Business Intelligence and Analytics ConcentrationMSc Corporate FinanceMSc Data Analytics for BusinessMaster of Business AdministrationMaster of Business Administration 60 ECTSMaster of Business Administration 90 ECTSMaster of Business Administration 60 ECTSMaster of Business Administration 90 ECTSBachelors in International Management
For College Students

Time Complexity of Binary Search - An Overview

$$/$$

Though in the last segment itself, Rachit, with the help of 11 sorted cards deduced that Binary Search follows O(logn) time complexity, Aishwarya proves it mathemetically in the video below. In case you are not able to follow the derivation, please do not worry at all. All you need to remember is that binary search follows O(logn) time complexity i.e. if the number of elements in an array are doubled, the number of steps required to search for an element in the array increases by 1 only.

$$/$$

Video Transcript

 

So now we are going to see what is the time complexity of this binary search operation. So suppose I am given this array consisting of some elements and a target element x and I have to find whether x exists here or no. So now let me denote by t n the total number of comparisons which I'll be doing in my binary search operation. So here, given x what I'll do, I will first compare it with my mid element and check if they both are equal. So that requires one comparison. In the next step if they both come out to be unequal, I would then need to check whether x is greater than the mid value or x is smaller than the mid value. So that would also require one more comparison. And when I have made the comparison and concluded that x is suppose less than the mid value, I would repeat the same procedure again on half of this array. So if t n denotes the total number of comparisons required for an array of size n, it would also include doing and repeating the same procedure on the same array of half the size. So beyond these two comparisons I would also write the total number of comparisons required for an array of size n by two. So simplifying it, I would write it like this. Now, since my array has now been reduced to n by two length, I will be repeating the same procedure. So t n by two can similarly be broken down like I broke down T-N-T-N required two comparisons plus the number of comparisons required for n by two. So t of n by two can also be broken down like this two number of comparisons for comparing whether my mid element is equal to the target element and one more comparison for comparing if it is less than or greater than the mid element. So two number of comparisons for here and the time required for repeating the same procedure on an array of size n by four. All right, so this was step number one, this was step number two. This can be further simplified as so if my entire procedure takes k number of steps, then I would denote t n as here. You would notice that in the first step I was doing two number of comparisons outside of t n by two. So it was two into one. In my second step I was writing it as two into two plus t of n by four. So here for my nth step, for my KTH step I would write it as t n equals to two k plus what we'll see what this is. In the first step I was writing it as t n by two which is t of n upon two to the power one. In my second step I was writing it as t of n by four which can also equivalent be written as t of n upon two square. So if you notice a pattern in all these steps, you would see that in my KTH step I would be requiring two k number of comparisons plus the total number of comparisons required for t of n upon two to the power k. You can also verify it for k equals to one and k equals to two. Here on plugging in k equals to one we get this which is two plus t of n by two n upon two to the power one. And similarly when I plug in k equals to two I get the same expression which I get for k equals to two, which is two into two plus t of n upon two square. So my general expression for T of n would now be reduced to t n is equal to two k plus T of n upon two to the power k. So now we have arrived at our final expression. T n is equal to two K plus t of n upon two to the power K. Here k were the number of steps. Now k was an extra variable which we need to eliminate from here. So how many steps will it actually take before this algorithm terminates? If you think about it, you would see that this algorithm would terminate when we are left with exactly one element. So that would require t one number of comparisons. So basically after k number of steps, my end step would be such that I would have t of one here. So in that case this thing can be replaced as t one to find out what my end condition would be. So let me see that here t of n upon two to the power k, when it reaches t of one it would denote that my algorithm has ended. So it essentially means that n upon two to the power K would be equal to one. That is, N would be equal to two to the power K. Now, if you take logarithm of base two on both sides you would see that log of n to the base two would be equal to K. So here I have arrived at my K value which denotes the number of step required in this procedure. So I had to eliminate k from here to get my t n expression. So I would plug in the value of k equals to log n here in this expression. Now, so I would see that t of n is equal to two into k, which is two into plus this was reduced to t one, which was the ending condition. So this will become t of one. So this will be my final expression denoting t of n. So now if you look at this carefully here, t one is a constant. So while finding the time complexity or the theta value we can safely ignore t one. So now we are left with this expression that is two into log of n. Here again, the multiplicative two outside of this log n can also be ignored since it is also a constant. So ultimately my T of n would be reduced to theta of log n to the base two. That is, my T of n is equal to theta of log n to the base two. So now I have arrived at this conclusion that the time complexity required for my binary search operation is of theta log n. And how do you intuitively judge this? Well, we saw that in each step we were reducing our size of array to almost half. We were seeing how our target value compares with the mid value. And depending on that, we were immediately discarding one half of the array. So it makes sense, since in each step I'm reducing my array into half. So time required would be of the order of log n.

 

Video Recap

 

 The goal is to find whether a target element x exists in an array consisting of some elements.

  • The time complexity of binary search is denoted by t_n, which represents the total number of comparisons required to find x.

  • In the first step, x is compared with the mid element of the array, requiring one comparison.

  • If they are unequal, then x is checked to see if it's greater or smaller than the mid value, requiring one more comparison.

  • The same procedure is repeated again on half of the array.

  • tn can be broken down as 2 comparisons outside of t_n/2 and the number of comparisons required for n/2.

  • tn for the kth step is 2k plus t_n/2k.

  • The algorithm will terminate when there's only one element left, which requires t1 comparisons.

  • The end condition can be expressed as t_n/n = t1.

  • n/2k = 1, which means n = 2k.

  • Log of n to the base 2 equals k.

  • t of n = 2 log n + t_1.

  • The time complexity of binary search is theta(log n) to the base 2.

 

In the above video at timestamp 2:53, the instructor intends to write the following instead of 2.2-

T(n) = 2+2+T(n/4)
T(n) = 4+T(n/4)

 

In case you did not get an idea on how efficient Binary Search is when compared to Linear Search, watch this short video below to appreciate the fact.

$$/$$

Great! So as discussed in the video, binary search follows O(logn). This is considerably less than the number of steps an O(n) algorithm takes. Remember, to double the worst-case number of steps in linear search, you also need to double the number of elements in the database. So, if you have 16 elements in the database, linear search will take 16 steps in the worst case, and to double this, you need to change the number of elements to 32. This will make the number of steps required in the worst case 32. While in binary search, for 16 entries, you need 4 steps. To double this to 8, you need to change the number of entries to 256. Then, the algorithm will take eight steps in the worst case. So, binary search is far from sensitive to the number of entries in the database. You can look at the following table to gain more clarity on all of this:

 

Number of Elements                        O(n) Steps                                            logn Steps                                        
16164
32325
2562568
$$/$$