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

Analysis of Linear Search in Data Structure

$$/$$

There needs to be some measurement that tells you how efficient linear search is. You already learnt about this in the previous module on Algorithm Analysis. So, let’s now use it to analyse linear search.

$$/$$

Video Transcript

 

So now we'll look at the time analysis of the linear search algorithm. So you remember we took an array like this the last time we were discussing about linear search. So if I have to find suppose an element x here and I take my x equals to six. Now, in the very first step itself, I would see that this six equal to this six. So I found my element immediately. And how many steps did it take for me to find it? It took me exactly one number of comparisons to find that six exists here in this array. So this is what we call the best case scenario in which it takes the least number of comparisons to find a given element. Now, suppose I had to find an element y here, and suppose y was equal to nine. So I will sequentially compare nine to each and every element here and it is only when I reach the last of this array that I would see that I have finally found my element nine. So in this case, how many steps did it take for me to find nine? It took me exactly five number of steps to do so. So this would count as something which I call as my worst case, which requires the most number of comparisons. Now consider another case. Suppose I have to find an element z here and I take my z equals to one. Now again, for finding one here in this array, I would need to compare it with all these elements in this array and this would require a total number of five comparisons. So again, these two would come under what I called as my worst case scenarios. So in best cases such as this one, I require exactly one number of comparisons. So I would say that my time complexity in best case scenario is equal to order of one. And for these two cases I would say that they come under the worst case. 

 

And how many number of comparisons do they need? Well, I used five comparison s for both of these cases where five is the number of elements in this array. So if I have an array of n number of elements, I would need n number of steps in my worst case scenario. So in my worst case my complexity would be order n. So. 

 

Video Recap

 

  • The linear search algorithm is analyzed for its time complexity.

  • The best case scenario occurs when the element to be found is the first element in the array. It takes only one comparison to find the element.

  • The worst case scenario occurs when the element to be found is the last element in the array or not present in the array at all. It takes n number of comparisons to find the element where n is the number of elements in the array.

  • In the worst case scenario, the time complexity is order and in the best case scenario, it is order of one.

  • The time complexity of a linear search algorithm depends on the number of elements in the array.

Learn about linear search algorithm's time complexity in its best and worst case scenarios. Discover how many comparisons it takes to find the element to be searched, and how the number of elements in the array impacts the time complexity. Find out more about the order of one and order n in the time complexity of linear search algorithm.

 

As discussed, for an array with n entries, the algorithm takes n steps in the worst case. Hence, it follows O(n). In the video below, you will see how linear search fares if you’re looking to search for a card of your choice from an entire deck.

$$/$$

So, to search for the jack of spades, which was at the end of the list, it took as many steps as the number of cards in the deck. Now, before we move on to the next search algorithm, let’s learn about something called divide and conquer in the next segment, this helps in increasing the efficiency of searching.