After implementation (Posterior analysis)<\/li>\n<\/ul>\n1. Prior Analysis<\/h4>\n
This analysis is done right after designing the algorithm. The prior analysis is a theoretical analysis where we measure the efficiency of an algorithm by assuming that factors such as processor speed do not affect efficiency.<\/p>\n
2. Posterior Analysis<\/h4>\n
It is the practical analysis of the implemented algorithm. It takes into consideration all the factors such as processor speed, the language in which it is implemented, the hardware involved, etc.<\/p>\n
Why analysis?<\/h3>\n
1. It is possible that for a single problem, there are multiple types of solutions possible i.e. one problem can have multiple algorithms that can solve the problem.<\/p>\n
2. For example, if we wish to sort a given sequence of numbers, we can do that using a sorting algorithm.<\/p>\n
3. There are multiple types of sorting. In fact, there are almost 150 types of sorting in all.<\/p>\n
4. In such a case, we need to decide which algorithm or logic is the best for solving our problem in terms of computation time and space occupied inside the memory.<\/p>\n
5. This is where analysis of an algorithm comes into the picture.<\/p>\n
Issues of an algorithm<\/h3>\n
There are majorly two factors that we need to decide through algorithm analysis. These factors are:<\/p>\n
1. When can we call an algorithm better than other algorithms for finding the solution to the same problem?<\/p>\n
2. What are the criteria of decision\/measurement to check which algorithm will perform better?<\/p>\n
An algorithm will be better than other algorithms depending upon various criteria for measurement which check the efficiency of any algorithm.<\/p>\n
Criteria for measurement of algorithm efficiency<\/h3>\n
There are two criteria used for the measurement\/analysis of the efficiency of any algorithm. These criteria are:<\/p>\n
1. Running time of the algorithm<\/p>\n
2. Space\/memory occupied by the algorithm<\/p>\n
Here we are talking about measuring the efficiency of algorithms, not the program.<\/p>\n
1. Running time of algorithm<\/h4>\n
a. The running time of an algorithm means how much time the algorithm will take to execute completely.<\/p>\n
b. But, an algorithm is just an abstract representation of a program. It is not the actual implementation.<\/p>\n
c. So, how can we find the running time of an algorithm?<\/p>\n
d. One way is to actually implement the algorithm into a program and see the time that this program takes for execution. This is the \u2018Experimental method\u2019.<\/p>\n
e. However, the experimental method has many limitations such as:<\/p>\n
i. It is difficult to sit and measure how much time a program takes to execute.<\/p>\n
ii. We don\u2019t know the range of input values, which is why we need to manually check for a wide variety of inputs by running the program a lot of times each time with different input. All this is cumbersome.<\/p>\n
iii. Whenever programming language comes into the picture, it comes with dependency on the machine. Therefore, depending on the machine\u2019s hardware and the operating system, the running time might vary on two different machines for the same set of code.<\/p>\n
iv. If we implement the same algorithm in C and Python, the running times will again vary. C is much faster than Python when it comes to running time. This is because of the presence of bulky modules in Python. Thus, we will get different running times in different programming languages.<\/p>\n
f. All these factors conclude that experimental analysis is not a good method to measure the efficiency of any algorithm.<\/p>\n
g. We want a generalised method independent of the machine, its hardware, software, programming language as well as capable of working on all possible input sizes.<\/p>\n
h. In general, running time will always depend upon input size. Thus, an increase in input size will always increase the running time. This is the basis of our running time analysis.<\/p>\n
i. In the whole algorithm analysis, we never measure the accurate running time for any algorithm, rather, we do approximations. We describe it as an asymptotic analysis.<\/p>\n
2. Space\/Memory<\/h4>\n
a. This is yet another parameter for analysing any algorithm.<\/p>\n
b. The space complexity of any algorithm is the total amount of space\/memory occupied by the algorithm concerning the input size.<\/p>\n
Let us understand the concept of space complexity using an example. Here, we\u2019ll try to compute the power of a number using two different ways:<\/p>\n
i. Using iterative approach<\/p>\n
ii. Using recursive approach<\/p>\n
and then check out their space complexities.<\/p>\n
i. Iterative approach<\/h5>\n
When we follow the iterative approach to find the power of a number, we make use of local variables. Here, we are using four variables- \u2018base\u2019, \u2018exponent\u2019, \u2018power\u2019, \u2018i\u2019 as shown:<\/p>\n
int pow_iterative(int base, int exponent)\n{\n for(i=0; i<exponent; i++)\n power = power*base;\n}\n<\/pre>\nHere, we just use four auto variables. Thus, the space occupied by this program is of constant order.<\/p>\n
ii. Recursive approach<\/h5>\n
Whenever recursion comes into the picture, stack as well comes along with it because recursion uses the stack for implementation.<\/p>\n
While performing recursion, we call the function again and again, which increases the memory used by the program.<\/p>\n
The recursive algorithm will be as follows:<\/p>\n
{\n if(exponent == 1)\n return base;\n return base * pow_recursive(base, exponent-1);\n}\n<\/pre>\nDue to the usage of the stack in recursion, this program has space complexity of the order \u2018n\u2019 i.e. linear order which is higher than constant order.<\/p>\n
So, we can conclude here that, in terms of space complexity, the iterative approach to find the power of a number is better and more efficient than the recursive approach to computing the same problem.<\/p>\n
Algorithmic complexity<\/h3>\n
By now, we have understood that the performance of an algorithm is measured in two factors- running time, memory used. Based on these two factors, an algorithm has the following two forms of complexity:<\/p>\n
1. Time complexity<\/h4>\n
Time complexity is defined as the amount of time taken by the algorithm for its completion. To calculate the time complexity, we calculate the number of steps an algorithm will take to execute.<\/p>\n
2. Space complexity<\/h4>\n
It is the total memory acquired by the process while executing.<\/p>\n
Design of an algorithm<\/h3>\n
1. There are many ways and approaches to design any algorithm.<\/p>\n
2. While designing an algorithm, we must keep in mind the running time of that algorithm and the memory that the algorithm will be using.<\/p>\n
3. Thus, during the design of an algorithm, we make use of that approach out of all the possible approaches, which gives the best results in terms of efficiency.<\/p>\n
4. We try to minimise the time and space complexity of the algorithm while designing an algorithm for a particular problem.<\/p>\n
Approaches of algorithm<\/h3>\n
There are many standard approaches to design an algorithm based on different strategies. A few of these are:<\/p>\n
1. Brute force technique<\/h4>\n
It is the general and the simplest way to design an algorithm. It simply involves a direct logic-based structure to design an algorithm. This is also called an \u2018Exhaustive search algorithm\u2019.<\/p>\n
2. Divide and conquer approach<\/h4>\n
This approach is based on dividing the problem into smaller sub-problems and solving those sub-problems. Once the subproblems are solved, we combine the solutions of those subproblems to get the final solution.<\/p>\n
3. Greedy method<\/h4>\n
This algorithm makes optimal choices at every iteration to get the best possible solution.<\/p>\n
4. Dynamic programming<\/h4>\n
It stores intermediate results to improve the efficiency of the algorithm. It is a recursion-based optimization algorithm. In dynamic programming, we store the results of sub-problems as well so that we don\u2019t need to re-compute even those sub-problems.<\/p>\n
5. Randomized algorithm<\/h4>\n
As the name suggests, this algorithm makes use of random numbers to decide the next step in the algorithm. It involves a certain degree of randomness in its logic. This randomness is involved to reduce the complexity of the algorithm over other standard algorithms.<\/p>\n
6. Backtracking<\/h4>\n
It also solves problems recursively. It involves searching every possible combination for solving a computational problem and removing those sub-solutions that don\u2019t satisfy the constraints of the problem.<\/p>\n
7. Branch and bound<\/h4>\n
It is an optimization algorithm used to solve combinatory, discrete and general mathematical problems. It involves dividing the problem, obtaining sub-solutions for them and then finding the most optimal solution.<\/p>\n
Techniques used for designing different algorithms are also termed algorithm design patterns.<\/p>\n
Designing the technique of an algorithm plays a very important role in the computation process as it will decide the computation time and memory occupied by the algorithm.<\/p>\n
Categories of algorithms<\/h3>\n1. Search<\/h4>\n
Algorithm used to search for a particular item in a data structure.<\/p>\n
2. Sort<\/h4>\n
Algorithm to sort the elements in a particular order.<\/p>\n
3. Delete<\/h4>\n
Algorithm used to delete a particular element from a data structure.<\/p>\n
4. Insert<\/h4>\n
Algorithm to insert a particular item in a data structure.<\/p>\n
5. Update<\/h4>\n
Algorithm used for updating the existing elements in a data structure.<\/p>\n
Types of algorithms<\/h3>\n
There are majorly two types of algorithms: searching algorithms and sorting algorithms.<\/p>\n
1. Searching algorithm<\/h4>\n
a. To search for a particular memory location or a particular value out of a huge chunk of data present inside the computer memory, we use searching algorithm techniques.<\/p>\n
b. There are various types of search techniques such as linear search, binary search, etc.<\/p>\n
2. Sorting algorithm<\/h4>\n
a. Sorting techniques are used in data structures to rearrange the values in a particular order.<\/p>\n
b. The order could be increasing, decreasing, non-increasing, non-decreasing, etc.<\/p>\n
Need for sorting algorithms<\/h3>\n
a. For optimizing the efficiency of other algorithms such as binary search.<\/p>\n
b. For producing information in a sorted order as it is more readable.<\/p>\n
c. Searching a particular element in a sorted list is easier than in an unsorted list.<\/p>\n
Conclusion<\/h3>\n
This article gives an overview of what an algorithm is in computer science and its importance in the computation process. Any good programmer will first design and analyze the software before implementing it. This is why writing algorithms before implementing solutions to a particular problem is a preferred approach. This makes algorithms very important from the aspect of solving computational problems.<\/p>\n
In the next article, we will study asymptotic analysis and how exactly we measure the complexities of any algorithm.<\/p>\n","protected":false},"excerpt":{"rendered":"
This is an introductory article on algorithms in data structure. In this article, we are going to get a brief overview of algorithms, the role of algorithms in computing and the overview of majorly...<\/p>\n","protected":false},"author":1,"featured_media":81097,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[3555],"tags":[3549,3550,3551,3552,3553,3554,3556,3557,3558],"class_list":["post-81057","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-data-structure","tag-algorithmic-complexity","tag-approaches-of-algorithm","tag-categories-of-algorithms","tag-characteristics-of-algorithm","tag-data-structure-algorithm","tag-data-structure-and-algorithm","tag-factors-of-an-algorithm","tag-need-for-sorting-algorithms","tag-types-of-algorithms"],"yoast_head":"\n
Data Structure and Algorithm - TechVidvan<\/title>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/techvidvan.com\/tutorials\/data-structure-and-algorithm\/\" \/>\n<meta property=\"og:locale\" content=\"en_US\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"Data Structure and Algorithm - TechVidvan\" \/>\n<meta property=\"og:description\" content=\"This is an introductory article on algorithms in data structure. In this article, we are going to get a brief overview of algorithms, the role of algorithms in computing and the overview of majorly...\" \/>\n<meta property=\"og:url\" content=\"https:\/\/techvidvan.com\/tutorials\/data-structure-and-algorithm\/\" \/>\n<meta property=\"og:site_name\" content=\"TechVidvan\" \/>\n<meta property=\"article:publisher\" content=\"https:\/\/www.facebook.com\/TechVidvan\/\" \/>\n<meta property=\"article:published_time\" content=\"2021-06-16T03:30:44+00:00\" \/>\n<meta property=\"og:image\" content=\"https:\/\/techvidvan.com\/tutorials\/wp-content\/uploads\/2021\/06\/DS-Algorithm.jpg\" \/>\n\t<meta property=\"og:image:width\" content=\"1200\" \/>\n\t<meta property=\"og:image:height\" content=\"628\" \/>\n\t<meta property=\"og:image:type\" content=\"image\/jpeg\" \/>\n<meta name=\"author\" content=\"TechVidvan Team\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<meta name=\"twitter:creator\" content=\"@vidvantech\" \/>\n<meta name=\"twitter:site\" content=\"@vidvantech\" \/>\n<meta name=\"twitter:label1\" content=\"Written by\" \/>\n\t<meta name=\"twitter:data1\" content=\"TechVidvan Team\" \/>\n\t<meta name=\"twitter:label2\" content=\"Est. reading time\" \/>\n\t<meta name=\"twitter:data2\" content=\"13 minutes\" \/>\n<!-- \/ Yoast SEO plugin. -->","yoast_head_json":{"title":"Data Structure and Algorithm - TechVidvan","robots":{"index":"index","follow":"follow","max-snippet":"max-snippet:-1","max-image-preview":"max-image-preview:large","max-video-preview":"max-video-preview:-1"},"canonical":"https:\/\/techvidvan.com\/tutorials\/data-structure-and-algorithm\/","og_locale":"en_US","og_type":"article","og_title":"Data Structure and Algorithm - TechVidvan","og_description":"This is an introductory article on algorithms in data structure. In this article, we are going to get a brief overview of algorithms, the role of algorithms in computing and the overview of majorly...","og_url":"https:\/\/techvidvan.com\/tutorials\/data-structure-and-algorithm\/","og_site_name":"TechVidvan","article_publisher":"https:\/\/www.facebook.com\/TechVidvan\/","article_published_time":"2021-06-16T03:30:44+00:00","og_image":[{"width":1200,"height":628,"url":"https:\/\/techvidvan.com\/tutorials\/wp-content\/uploads\/2021\/06\/DS-Algorithm.jpg","type":"image\/jpeg"}],"author":"TechVidvan Team","twitter_card":"summary_large_image","twitter_creator":"@vidvantech","twitter_site":"@vidvantech","twitter_misc":{"Written by":"TechVidvan Team","Est. reading time":"13 minutes"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"Article","@id":"https:\/\/techvidvan.com\/tutorials\/data-structure-and-algorithm\/#article","isPartOf":{"@id":"https:\/\/techvidvan.com\/tutorials\/data-structure-and-algorithm\/"},"author":{"name":"TechVidvan Team","@id":"https:\/\/techvidvan.com\/tutorials\/#\/schema\/person\/e9c26e74dd3d87421f7ada9433b8cd22"},"headline":"Data Structure and Algorithm","datePublished":"2021-06-16T03:30:44+00:00","mainEntityOfPage":{"@id":"https:\/\/techvidvan.com\/tutorials\/data-structure-and-algorithm\/"},"wordCount":2605,"commentCount":0,"publisher":{"@id":"https:\/\/techvidvan.com\/tutorials\/#organization"},"image":{"@id":"https:\/\/techvidvan.com\/tutorials\/data-structure-and-algorithm\/#primaryimage"},"thumbnailUrl":"https:\/\/techvidvan.com\/tutorials\/wp-content\/uploads\/2021\/06\/DS-Algorithm.jpg","keywords":["Algorithmic complexity","Approaches of algorithm","Categories of algorithms","Characteristics of algorithm","Data Structure Algorithm","Data Structure and Algorithm","Factors of an algorithm","Need for sorting algorithms","Types of algorithms"],"articleSection":["Data Structure Tutorials"],"inLanguage":"en-US","potentialAction":[{"@type":"CommentAction","name":"Comment","target":["https:\/\/techvidvan.com\/tutorials\/data-structure-and-algorithm\/#respond"]}]},{"@type":"WebPage","@id":"https:\/\/techvidvan.com\/tutorials\/data-structure-and-algorithm\/","url":"https:\/\/techvidvan.com\/tutorials\/data-structure-and-algorithm\/","name":"Data Structure and Algorithm - TechVidvan","isPartOf":{"@id":"https:\/\/techvidvan.com\/tutorials\/#website"},"primaryImageOfPage":{"@id":"https:\/\/techvidvan.com\/tutorials\/data-structure-and-algorithm\/#primaryimage"},"image":{"@id":"https:\/\/techvidvan.com\/tutorials\/data-structure-and-algorithm\/#primaryimage"},"thumbnailUrl":"https:\/\/techvidvan.com\/tutorials\/wp-content\/uploads\/2021\/06\/DS-Algorithm.jpg","datePublished":"2021-06-16T03:30:44+00:00","breadcrumb":{"@id":"https:\/\/techvidvan.com\/tutorials\/data-structure-and-algorithm\/#breadcrumb"},"inLanguage":"en-US","potentialAction":[{"@type":"ReadAction","target":["https:\/\/techvidvan.com\/tutorials\/data-structure-and-algorithm\/"]}]},{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/techvidvan.com\/tutorials\/data-structure-and-algorithm\/#primaryimage","url":"https:\/\/techvidvan.com\/tutorials\/wp-content\/uploads\/2021\/06\/DS-Algorithm.jpg","contentUrl":"https:\/\/techvidvan.com\/tutorials\/wp-content\/uploads\/2021\/06\/DS-Algorithm.jpg","width":1200,"height":628,"caption":"Data Structure and Algorithm"},{"@type":"BreadcrumbList","@id":"https:\/\/techvidvan.com\/tutorials\/data-structure-and-algorithm\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"Home","item":"https:\/\/techvidvan.com\/tutorials\/"},{"@type":"ListItem","position":2,"name":"Data Structure and Algorithm"}]},{"@type":"WebSite","@id":"https:\/\/techvidvan.com\/tutorials\/#website","url":"https:\/\/techvidvan.com\/tutorials\/","name":"TechVidvan Blogs","description":"","publisher":{"@id":"https:\/\/techvidvan.com\/tutorials\/#organization"},"potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/techvidvan.com\/tutorials\/?s={search_term_string}"},"query-input":{"@type":"PropertyValueSpecification","valueRequired":true,"valueName":"search_term_string"}}],"inLanguage":"en-US"},{"@type":"Organization","@id":"https:\/\/techvidvan.com\/tutorials\/#organization","name":"TechVidvan","url":"https:\/\/techvidvan.com\/tutorials\/","logo":{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/techvidvan.com\/tutorials\/#\/schema\/logo\/image\/","url":"https:\/\/techvidvan.com\/tutorials\/wp-content\/uploads\/2024\/03\/techvidvan-logo-200x50-1.webp","contentUrl":"https:\/\/techvidvan.com\/tutorials\/wp-content\/uploads\/2024\/03\/techvidvan-logo-200x50-1.webp","width":200,"height":50,"caption":"TechVidvan"},"image":{"@id":"https:\/\/techvidvan.com\/tutorials\/#\/schema\/logo\/image\/"},"sameAs":["https:\/\/www.facebook.com\/TechVidvan\/","https:\/\/x.com\/vidvantech"]},{"@type":"Person","@id":"https:\/\/techvidvan.com\/tutorials\/#\/schema\/person\/e9c26e74dd3d87421f7ada9433b8cd22","name":"TechVidvan Team","description":"The TechVidvan Team delivers practical, beginner-friendly tutorials on programming, Java, Python, C++, DSA, AI, ML, data Science, Android, Flutter, MERN, Web Development, and technology. Our experts are here to help you upskill and excel in today\u2019s tech industry."}]}},"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/techvidvan.com\/tutorials\/wp-json\/wp\/v2\/posts\/81057","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/techvidvan.com\/tutorials\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/techvidvan.com\/tutorials\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/techvidvan.com\/tutorials\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/techvidvan.com\/tutorials\/wp-json\/wp\/v2\/comments?post=81057"}],"version-history":[{"count":0,"href":"https:\/\/techvidvan.com\/tutorials\/wp-json\/wp\/v2\/posts\/81057\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/techvidvan.com\/tutorials\/wp-json\/wp\/v2\/media\/81097"}],"wp:attachment":[{"href":"https:\/\/techvidvan.com\/tutorials\/wp-json\/wp\/v2\/media?parent=81057"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/techvidvan.com\/tutorials\/wp-json\/wp\/v2\/categories?post=81057"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/techvidvan.com\/tutorials\/wp-json\/wp\/v2\/tags?post=81057"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}![\"Algorithm](\"https:\/\/techvidvan.com\/tutorials\/wp-content\/uploads\/sites\/2\/2021\/06\/Algorithm-Design-and-Analysis.jpg\")
<\/a><\/p>\n![\"Factors](\"https:\/\/techvidvan.com\/tutorials\/wp-content\/uploads\/sites\/2\/2021\/06\/Factors-of-an-algorithm-1.jpg\")
<\/a><\/p>\n