Skip to content
codingtube

codingtube

Coding and Programming tutorials

  • javascript
  • React
  • ES6
  • React js
  • coding
  • ffmpeg
  • java
  • programming
  • information
  • coding
  • Privacy Policy
  • Twitter trends
  • Age Calculatore
  • Codingtube Community
  • YouTube Tags Generator
  • About
  • Toggle search form

Algorithm Efficiency in data structure

Posted on December 11, 2021December 11, 2021 By christo No Comments on Algorithm Efficiency in data structure

If a function is linear (without any loops or recursions), the efficiency of that algorithm or the running time of that algorithm can be given as the number of instructions it contains. However, if an algorithm contains loops, then the efficiency of that algorithm may vary depending on the number of loops and the running time of each loop in the algorithm

Let us consider different cases in which loops determine the efficiency of an algorithm

Linear Loops

To calculate the efficiency of an algorithm that has a single loop, we need to first determine the number of times the statements in the loop will be executed. This is because the number of iterations is directly proportional to the loop factor. Greater the loop factor, more is the number of iterations. For example, consider the loop given below:

for(i=0;i<100;i++)
statement block;

Here, 100 is the loop factor. We have already said that efficiency is directly proportional to the number of iterations. Hence, the general formula in the case of linear loops may be given as

f(n) = n

However calculating efficiency is not as simple as is shown in the above example. Consider the loop given below:

for(i=0;i<100;i+=2)
 statement block;

Here, the number of iterations is half the number of the loop factor. So, here the efficiency can be given as

f(n) = n/2

Logarithmic Loops

In logarithmic loops, the loop-controlling variable is either multiplied or divided during each iteration of the loop. For example, look at the loops given below

for(i=1;i<1000;i*=2) for(i=1000;i>=1;i/=2)
statement block; statement block;

Nested Loops

Loops that contain loops are known as nested loops. In order to analyse nested loops, we need to determine the number of iterations each loop completes. The total is then obtained as the product of the number of iterations in the inner loop and the number of iterations in the outer loop

In this case, we analyse the efficiency of the algorithm based on whether it is a linear logarithmic, quadratic, or dependent quadratic nested loop.

Linear logarithmic loop Consider the following code in which the loop-controlling variable of the inner loop is multiplied after each iteration. The number of iterations in the inner loop is log 10. This inner loop is controlled by an outer loop which iterates 10 times. Therefore, according to the formula, the number of iterations for this code can be given as 10 log 10.

for(i=0;i<10;i++)
for(j=1; j<10;j*=2)
 statement block;

Quadratic loop In a quadratic loop, the number of iterations in the inner loop is equal to the number of iterations in the outer loop. Consider the following code in which the outer loop executes 10 times and for each iteration of the outer loop, the inner loop also executes 10 times. Therefore, the efficiency here is 100

for(i=0;i<10;i++)
for(j=0; j<10;j++)
 statement block;

The generalized formula for quadratic loop can be given as f(n) = n2

Dependent quadratic loop In a dependent quadratic loop, the number of iterations in the inner loop is dependent on the outer loop. Consider the code given below:

for(i=0;i<10;i++)
for(j=0; j<=i;j++)
 statement block;

In this code, the inner loop will execute just once in the first iteration, twice in the second iteration, thrice in the third iteration, so on and so forth. In this way, the number of iterations can be calculated as

1 + 2 + 3 + … + 9 + 10 = 55
.

data structure Tags:Algorithm Efficiency in data structure

Post navigation

Previous Post: Control Structures Used In Algorithms
Next Post: Big O Notation in data structure

Related Posts

Header Linked Lists using C data structure
java program of Binary tree in data structure data structure
Leetcode Two Sum II – Input array is sorted using java data structure
C program of Merge Sort For Linked List data structure
Complete Binary Trees data structure
C program to implement a priority queue data structure

Leave a Reply Cancel reply

You must be logged in to post a comment.

Recent Posts

  • Affiliate Marketing Principles
  • The Basics You Need to Know About Affiliate Marketing
  • Affiliate Marketing Options
  • All About Affiliate Marketing
  • Classification of Database Management Systems
  • Three-Tier and n-Tier Architectures
    for Web Applications
  • Two-Tier Client/Server Architectures for DBMSs
  • Basic Client/Server Architectures in DBMS
  • Centralized DBMSs Architecture in DBMS
  • Tools, Application Environments, and Communications Facilities in DBMS

Categories

  • Affiliate marketing (5)
  • Algorithm (43)
  • amp (3)
  • android (223)
  • Android App (8)
  • Android app review (4)
  • android tutorial (60)
  • Artificial intelligence (61)
  • AWS (3)
  • bitcoin (8)
  • blockchain (1)
  • c (5)
  • c language (105)
  • cloud computing (4)
  • coding (4)
  • coding app (4)
  • complex number (1)
  • Computer Graphics (66)
  • data compression (65)
  • data structure (188)
  • DBMS (44)
  • digital marketing (9)
  • distributed systems (11)
  • ffmpeg (26)
  • game (3)
  • html (6)
  • image processing (35)
  • Inequalities (1)
  • information (4)
  • java (212)
  • java network (1)
  • javascript (9)
  • kotlin (4)
  • leetcode (1)
  • math (21)
  • maven (1)
  • mysql (1)
  • Node.js (8)
  • operating system (109)
  • php (310)
  • Principle Of Mathematical Induction (1)
  • programming (6)
  • Python (4)
  • Python data structure (9)
  • React native (1)
  • React.js (22)
  • Redux (1)
  • seo (4)
  • set (12)
  • trigonometry (6)
  • vue.js (35)
  • XML (3)

sitemap

sitemap of videos

sitemap of webstories

sitemap of website

  • Affiliate marketing
  • Algorithm
  • amp
  • android
  • Android App
  • Android app review
  • android tutorial
  • Artificial intelligence
  • AWS
  • bitcoin
  • blockchain
  • c
  • c language
  • cloud computing
  • coding
  • coding app
  • complex number
  • Computer Graphics
  • data compression
  • data structure
  • DBMS
  • digital marketing
  • distributed systems
  • ffmpeg
  • game
  • html
  • image processing
  • Inequalities
  • information
  • java
  • java network
  • javascript
  • kotlin
  • leetcode
  • math
  • maven
  • mysql
  • Node.js
  • operating system
  • php
  • Principle Of Mathematical Induction
  • programming
  • Python
  • Python data structure
  • React native
  • React.js
  • Redux
  • seo
  • set
  • trigonometry
  • vue.js
  • XML
  • Blog
  • Data compression tutorial - codingpoint
  • How to change mbstring in php 5.6
  • How to diagnose out of memory killed PHP-FPM
  • Introduction to jQuery
  • Privacy
  • Affiliate marketing
  • Algorithm
  • amp
  • android
  • Android App
  • Android app review
  • android tutorial
  • Artificial intelligence
  • AWS
  • bitcoin
  • blockchain
  • c
  • c language
  • cloud computing
  • coding
  • coding app
  • complex number
  • Computer Graphics
  • data compression
  • data structure
  • DBMS
  • digital marketing
  • distributed systems
  • ffmpeg
  • game
  • html
  • image processing
  • Inequalities
  • information
  • java
  • java network
  • javascript
  • kotlin
  • leetcode
  • math
  • maven
  • mysql
  • Node.js
  • operating system
  • php
  • Principle Of Mathematical Induction
  • programming
  • Python
  • Python data structure
  • React native
  • React.js
  • Redux
  • seo
  • set
  • trigonometry
  • vue.js
  • XML
  • Blog
  • Data compression tutorial - codingpoint
  • How to change mbstring in php 5.6
  • How to diagnose out of memory killed PHP-FPM
  • Introduction to jQuery
  • Privacy

© codingtube.tech