Analysis of Recursive and Non-Recursive Complexity with Graph-Based Modeling

Analysis of Recursive and Non-Recursive Complexity with Graph-Based Modeling | Research Square window.SnipcartSettings = { analytics: { enabled: false } }; (function() { var accessVector = localStorage.getItem('access_vector') || ''; window.dataLayer = window.dataLayer || []; if (accessVector) { window.dataLayer.push({ user: { profile: { profileInfo: { snid: accessVector } } } }); } })(); (function(w,d,s,l,i){w[l]=w[l]||[];w[l].push({'gtm.start':new Date().getTime(),event:'gtm.js'});var f=d.getElementsByTagName(s)[0],j=d.createElement(s),dl=l!='dataLayer'?'&l='+l:'';j.async=true;j.src='https://www.googletagmanager.com/gtm.js?id='+i+dl;f.parentNode.insertBefore(j,f);})(window,document,'script','dataLayer','GTM-K279D39R'); Browse Preprints In Review Journals COVID-19 Preprints AJE Video Bytes Research Tools Research Promotion AJE Professional Editing AJE Rubriq About Preprint Platform In Review Editorial Policies Our Team Advisory Board Help Center Sign In Submit a Preprint Cite Share Download PDF Research Article Analysis of Recursive and Non-Recursive Complexity with Graph-Based Modeling Mohd. Izhar, Shafiqulabidin, Pinki Nayak, Faisal Rais This is a preprint; it has not been peer reviewed by a journal. https://doi.org/ 10.21203/rs.3.rs-7893355/v1 This work is licensed under a CC BY 4.0 License Status: Posted Version 1 posted You are reading this latest preprint version Abstract Master Theorem with systematic approach and as an essential tool is used to analyses the time complexity of divide and conquer algorithms , it can solve recurrence relation of the theorem of the form T(n)=aT(n/b)+f(n) where a represents the number of subproblems, n/b is the magnitude of each subproblem, and f(n) accounts for the non-recursive work. This paper studies the comparison of growth dynamics of recursive and non-recursive terms in order to classify and determine the asymptotic behaviors of recursive relations. Traditional methods provide the knowledge to an extent but fail in complex scenarios or are proved to be ineffective frequently while applied for solving the recurrence. Master theorem provides a coordinated view for solving the recursive relations by examining the relationship between the parameters, log b ⁡a and k, where f(n)=Θ(n^k log^p⁡(n) ) , It defines distinct cases for determining whether the recursive or non-recursive work dominates in the overall complexity. This paper examines three main cases with examples and shows where recursion controls, terms raise similarly, or non-recursive work succeeds. Practical examples such as Binary Search, Merge Sort, Strassen's Matrix Multiplication etc are analyzed both through traditional Master Theorem classification and graph-based visual modeling, providing clearer insight into their asymptotic behaviors. This combined approach streamlines the classification process, highlights dominance patterns more intuitively, and offers a new perspective on recurrence analysis in modern computational problems. Computer Architecture and Engineering Master Theorem divide-and-conquer algorithms time complexity analysis recurrence relations asymptotic behavior recursive work non-recursive work Full Text Additional Declarations The authors declare no competing interests. Cite Share Download PDF Status: Posted Version 1 posted You are reading this latest preprint version Research Square lets you share your work early, gain feedback from the community, and start making changes to your manuscript prior to peer review in a journal. As a division of Research Square Company, we’re committed to making research communication faster, fairer, and more useful. We do this by developing innovative software and high quality services for the global research community. Our growing team is made up of researchers and industry professionals working together to solve the most critical problems facing scientific publishing. Also discoverable on Platform About Our Team In Review Editorial Policies Advisory Board Help Center Resources Author Services Accessibility API Access RSS feed Manage Cookie Preferences © Research Square 2026 | ISSN 2693-5015 (online) Privacy Policy Terms of Service Do Not Sell My Personal Information {"props":{"pageProps":{"initialData":{"identity":"rs-7893355","acceptedTermsAndConditions":true,"allowDirectSubmit":true,"archivedVersions":[],"articleType":"Research Article","associatedPublications":[],"authors":[{"id":531607567,"identity":"186fc25c-740b-412e-a3e8-18f2360a0935","order_by":0,"name":"Mohd. Izhar","email":"","orcid":"","institution":"Dr. Akhilesh Dass Gupta Institute of Professional Studies (Approved by AICTE and Affiliated to GGSIPU Delhi, India","correspondingAuthor":false,"prefix":"","firstName":"Mohd.","middleName":"","lastName":"Izhar","suffix":""},{"id":531607634,"identity":"30a3b10f-21dc-4ed0-a143-9e191b40db0c","order_by":1,"name":"Shafiqulabidin","email":"","orcid":"","institution":"Department of Computer Science Aligarh Muslim University, Uttar Pradesh, INDIA","correspondingAuthor":false,"prefix":"","firstName":"","middleName":"","lastName":"Shafiqulabidin","suffix":""},{"id":531607635,"identity":"d7b00a7d-bfef-4c8e-9fd1-0621f6a9bcc5","order_by":2,"name":"Pinki Nayak","email":"data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAZAAAAAyAQMAAABI0h/eAAAABlBMVEX///8AAABVwtN+AAAACXBIWXMAAA7EAAAOxAGVKw4bAAABBUlEQVRIiWNgGAWjYDACZiBMALPYGBh4GBjkQMwDD0jRYgzWkkDIHgYkLYkNIDY+LebsvIcNHjDckTc4fiyB4W2bXfr8sMMPgbbYyek2YNdi2cyXnJDA8Mxww5m0A4xz25JzN95OMwBqSTY2O4Bdi8FhHmOggsOMGw6kNzDztjHnbpydANJyIHEbAS32G84/B2mpTzecnf6BoBagww4nbriRdgCo5XCCvHQOflssm3mMDRIMDifPvPEs4eCcc8cNN0jnFBxIMMDtF3P+M8aSPyoO2/adTzN88KasWl5+dvrmDx8q7ORweh9GKgAVgNUYHECI49ECBPIN6IxRMApGwSgYBVAAADGZY1iCsfaXAAAAAElFTkSuQmCC","orcid":"","institution":"Dr. Akhilesh Dass Gupta Institute of Professional Studies (Approved by AICTE and Affiliated to GGSIPU Delhi, India","correspondingAuthor":true,"prefix":"","firstName":"Pinki","middleName":"","lastName":"Nayak","suffix":""},{"id":531607636,"identity":"aa51691b-75c5-4f93-a4cf-e91d85b89e00","order_by":3,"name":"Faisal Rais","email":"","orcid":"","institution":"Dr. Akhilesh Dass Gupta Institute of Professional Studies (Approved by AICTE and Affiliated to GGSIPU Delhi, India","correspondingAuthor":false,"prefix":"","firstName":"Faisal","middleName":"","lastName":"Rais","suffix":""}],"badges":[],"createdAt":"2025-10-18 12:10:15","currentVersionCode":1,"declarations":{"humanSubjects":false,"vertebrateSubjects":false,"conflictsOfInterestStatement":false,"humanSubjectEthicalGuidelines":false,"humanSubjectConsent":false,"humanSubjectClinicalTrial":false,"humanSubjectCaseReport":false,"vertebrateSubjectEthicalGuidelines":false},"doi":"10.21203/rs.3.rs-7893355/v1","doiUrl":"https://doi.org/10.21203/rs.3.rs-7893355/v1","draftVersion":[],"editorialEvents":[],"editorialNote":"","failedWorkflow":false,"files":[{"id":93985449,"identity":"a4751fe9-301d-4baa-9976-cf78c8af1632","added_by":"auto","created_at":"2025-10-21 04:09:20","extension":"docx","order_by":0,"title":"","display":"","copyAsset":false,"role":"acdc-reference","size":1551946,"visible":true,"origin":"","legend":"","description":"","filename":"preprintupload18102025ModifiedMaster.docx","url":"https://assets-eu.researchsquare.com/files/rs-7893355/v1/7a71fb91d18a7275906fd849.docx"},{"id":93985439,"identity":"2e31a05f-c8a3-4d4b-9f52-740da566b4b5","added_by":"auto","created_at":"2025-10-21 04:09:20","extension":"json","order_by":1,"title":"","display":"","copyAsset":false,"role":"acdc-reference","size":342,"visible":true,"origin":"","legend":"","description":"","filename":"rs7893355.json","url":"https://assets-eu.researchsquare.com/files/rs-7893355/v1/57cb9764ea56e17a19ff6530.json"},{"id":93985446,"identity":"5dd8b13d-6dae-4684-9873-e175c7f2cb70","added_by":"auto","created_at":"2025-10-21 04:09:20","extension":"xml","order_by":2,"title":"","display":"","copyAsset":false,"role":"acdc-reference","size":85541,"visible":true,"origin":"","legend":"","description":"","filename":"rs78933550enriched.xml","url":"https://assets-eu.researchsquare.com/files/rs-7893355/v1/56ef52910a91aa259fc91b48.xml"},{"id":93985447,"identity":"6dad4b87-1aa2-4a54-8730-96b7f354c8db","added_by":"auto","created_at":"2025-10-21 04:09:20","extension":"png","order_by":3,"title":"","display":"","copyAsset":false,"role":"acdc-reference","size":1307757,"visible":true,"origin":"","legend":"","description":"","filename":"floatimage1.png","url":"https://assets-eu.researchsquare.com/files/rs-7893355/v1/ef8edb6440e3c45aaab61afb.png"},{"id":93986383,"identity":"d5d0e428-b69d-436f-b0c4-048c0887852f","added_by":"auto","created_at":"2025-10-21 04:17:20","extension":"png","order_by":4,"title":"","display":"","copyAsset":false,"role":"acdc-reference","size":26999,"visible":true,"origin":"","legend":"","description":"","filename":"floatimage2.png","url":"https://assets-eu.researchsquare.com/files/rs-7893355/v1/54ffa2452889dafc7826f1f2.png"},{"id":93985442,"identity":"7fe2ca4e-5bee-4293-87a7-ae4a10aa9208","added_by":"auto","created_at":"2025-10-21 04:09:20","extension":"png","order_by":5,"title":"","display":"","copyAsset":false,"role":"acdc-reference","size":34998,"visible":true,"origin":"","legend":"","description":"","filename":"floatimage3.png","url":"https://assets-eu.researchsquare.com/files/rs-7893355/v1/07195bfff82987750c7dec76.png"},{"id":93985443,"identity":"d510b955-7de3-4e45-b024-d68845241407","added_by":"auto","created_at":"2025-10-21 04:09:20","extension":"png","order_by":6,"title":"","display":"","copyAsset":false,"role":"acdc-reference","size":34704,"visible":true,"origin":"","legend":"","description":"","filename":"floatimage4.png","url":"https://assets-eu.researchsquare.com/files/rs-7893355/v1/5cdddd269b3bed5bc0f279c2.png"},{"id":93985451,"identity":"e65399d6-f738-4a19-a92b-71be17f4bce0","added_by":"auto","created_at":"2025-10-21 04:09:20","extension":"png","order_by":7,"title":"","display":"","copyAsset":false,"role":"acdc-reference","size":31243,"visible":true,"origin":"","legend":"","description":"","filename":"floatimage5.png","url":"https://assets-eu.researchsquare.com/files/rs-7893355/v1/7f6c0c3514f8ea565624ba5e.png"},{"id":93985440,"identity":"fa194a95-f939-4365-9fd9-5a09cd2362f0","added_by":"auto","created_at":"2025-10-21 04:09:20","extension":"png","order_by":8,"title":"","display":"","copyAsset":false,"role":"acdc-reference","size":36923,"visible":true,"origin":"","legend":"","description":"","filename":"floatimage6.png","url":"https://assets-eu.researchsquare.com/files/rs-7893355/v1/95439c818f220e15dc0c0501.png"},{"id":93986384,"identity":"690dcad4-2a70-4f3a-b60b-3d39c4836c0f","added_by":"auto","created_at":"2025-10-21 04:17:20","extension":"png","order_by":9,"title":"","display":"","copyAsset":false,"role":"acdc-reference","size":29533,"visible":true,"origin":"","legend":"","description":"","filename":"floatimage7.png","url":"https://assets-eu.researchsquare.com/files/rs-7893355/v1/0f69e562110f980528033f90.png"},{"id":93986387,"identity":"00f68244-5802-4ead-b08f-5bfec84632c6","added_by":"auto","created_at":"2025-10-21 04:17:20","extension":"png","order_by":10,"title":"","display":"","copyAsset":false,"role":"acdc-reference","size":56747,"visible":true,"origin":"","legend":"","description":"","filename":"Onlinefloatimage1.png","url":"https://assets-eu.researchsquare.com/files/rs-7893355/v1/1b3da9f00bd1a8222b931330.png"},{"id":93986388,"identity":"7ad436f9-1bfa-4a50-990d-c57af527a5c4","added_by":"auto","created_at":"2025-10-21 04:17:20","extension":"png","order_by":11,"title":"","display":"","copyAsset":false,"role":"acdc-reference","size":11494,"visible":true,"origin":"","legend":"","description":"","filename":"Onlinefloatimage2.png","url":"https://assets-eu.researchsquare.com/files/rs-7893355/v1/ee168c7a13f8ce842f3258af.png"},{"id":93985454,"identity":"6b27f9a7-0aee-44e6-b4d9-d0c429097056","added_by":"auto","created_at":"2025-10-21 04:09:20","extension":"png","order_by":12,"title":"","display":"","copyAsset":false,"role":"acdc-reference","size":11466,"visible":true,"origin":"","legend":"","description":"","filename":"Onlinefloatimage3.png","url":"https://assets-eu.researchsquare.com/files/rs-7893355/v1/bbc69a83a97bdcac3d44d943.png"},{"id":93985445,"identity":"d94aae2c-d982-48b3-9a73-6cec0d09bd74","added_by":"auto","created_at":"2025-10-21 04:09:20","extension":"png","order_by":13,"title":"","display":"","copyAsset":false,"role":"acdc-reference","size":10936,"visible":true,"origin":"","legend":"","description":"","filename":"Onlinefloatimage4.png","url":"https://assets-eu.researchsquare.com/files/rs-7893355/v1/0ecb4f5eca885a432fbce2b2.png"},{"id":93986385,"identity":"1168c3cf-f93c-44d2-829c-5b012150a4e4","added_by":"auto","created_at":"2025-10-21 04:17:20","extension":"png","order_by":14,"title":"","display":"","copyAsset":false,"role":"acdc-reference","size":10676,"visible":true,"origin":"","legend":"","description":"","filename":"Onlinefloatimage5.png","url":"https://assets-eu.researchsquare.com/files/rs-7893355/v1/f6352a78ec0d020c66e104da.png"},{"id":93985453,"identity":"f6519d85-8362-4fad-994f-f5f79b036765","added_by":"auto","created_at":"2025-10-21 04:09:20","extension":"png","order_by":15,"title":"","display":"","copyAsset":false,"role":"acdc-reference","size":11399,"visible":true,"origin":"","legend":"","description":"","filename":"Onlinefloatimage6.png","url":"https://assets-eu.researchsquare.com/files/rs-7893355/v1/b3f02f61ef8be2f8a6912234.png"},{"id":93986386,"identity":"2d2c6e71-229f-464e-8b4e-1df466f7e745","added_by":"auto","created_at":"2025-10-21 04:17:20","extension":"png","order_by":16,"title":"","display":"","copyAsset":false,"role":"acdc-reference","size":8465,"visible":true,"origin":"","legend":"","description":"","filename":"Onlinefloatimage7.png","url":"https://assets-eu.researchsquare.com/files/rs-7893355/v1/e9818244f9fa683f119ba42c.png"},{"id":93985456,"identity":"bf7ea5f8-6707-4ea5-936a-8b44941e1fc7","added_by":"auto","created_at":"2025-10-21 04:09:21","extension":"xml","order_by":17,"title":"","display":"","copyAsset":false,"role":"acdc-reference","size":80143,"visible":true,"origin":"","legend":"","description":"","filename":"rs78933550structuring.xml","url":"https://assets-eu.researchsquare.com/files/rs-7893355/v1/8caff78d448799b1414b7a46.xml"},{"id":93985458,"identity":"2fb89d0c-900d-4780-a8d9-790b74534cba","added_by":"auto","created_at":"2025-10-21 04:09:21","extension":"html","order_by":18,"title":"","display":"","copyAsset":false,"role":"acdc-reference","size":96972,"visible":true,"origin":"","legend":"","description":"","filename":"earlyproof.html","url":"https://assets-eu.researchsquare.com/files/rs-7893355/v1/00bf791fb752ed9a4a9efbbd.html"},{"id":93987007,"identity":"581079fd-3dbb-4a9a-a118-e1777ce44a7c","added_by":"auto","created_at":"2025-10-21 04:25:21","extension":"pdf","order_by":1,"title":"","display":"","copyAsset":false,"role":"manuscript-pdf","size":562069,"visible":true,"origin":"","legend":"","description":"","filename":"preprintupload18102025ModifiedMaster.pdf","url":"https://assets-eu.researchsquare.com/files/rs-7893355/v1_covered_1c61fb8a-e703-4740-94bb-d7a4c7218dc3.pdf"}],"financialInterests":"The authors declare no competing interests.","formattedTitle":"\u003cp\u003eAnalysis of Recursive and Non-Recursive Complexity with Graph-Based Modeling\u003c/p\u003e","fulltext":[],"fulltextSource":"","fullText":"","funders":[],"hasAdminPriorityOnWorkflow":false,"hasManuscriptDocX":false,"hasOptedInToPreprint":true,"hasPassedJournalQc":"","hasAnyPriority":true,"hideJournal":true,"highlight":"","institution":"","isAcceptedByJournal":false,"isAuthorSuppliedPdf":true,"isDeskRejected":"","isHiddenFromSearch":false,"isInQc":false,"isInWorkflow":false,"isPdf":true,"isPdfUpToDate":true,"isWithdrawnOrRetracted":false,"journal":{"display":true,"email":"[email protected]","identity":"researchsquare","isNatureJournal":false,"hasQc":true,"allowDirectSubmit":true,"externalIdentity":"","sideBox":"","snPcode":"","submissionUrl":"/submission","title":"Research Square","twitterHandle":"researchsquare","acdcEnabled":true,"dfaEnabled":false,"editorialSystem":"","reportingPortfolio":"","inReviewEnabled":false,"inReviewRevisionsEnabled":true},"keywords":"Master Theorem, divide-and-conquer algorithms, time complexity analysis, recurrence relations, asymptotic behavior, recursive work, non-recursive work","lastPublishedDoi":"10.21203/rs.3.rs-7893355/v1","lastPublishedDoiUrl":"https://doi.org/10.21203/rs.3.rs-7893355/v1","license":{"name":"CC BY 4.0","url":"https://creativecommons.org/licenses/by/4.0/"},"manuscriptAbstract":"\u003cp\u003eMaster Theorem with systematic approach and as an essential tool is used to analyses the time complexity of divide and conquer algorithms , it can solve recurrence relation of \u0026nbsp;the theorem of the form T(n)=aT(n/b)+f(n) where a represents the number of subproblems, n/b is the magnitude of each subproblem, and f(n) accounts for the non-recursive work. This paper studies the comparison of \u0026nbsp;\u0026nbsp;growth dynamics of recursive and non-recursive terms in order to classify and determine the asymptotic behaviors of recursive relations. Traditional methods provide the knowledge to an extent but fail in complex scenarios or are proved to be ineffective frequently while applied for solving the recurrence. Master theorem provides a coordinated view for solving the recursive relations by examining the relationship between the parameters, log\u003csub\u003eb\u003c/sub\u003e⁡a \u0026nbsp;and k, where f(n)=Θ(n^k \u0026nbsp;log^p⁡(n) ) , \u0026nbsp;It defines distinct cases for determining whether the recursive or non-recursive work dominates in the overall complexity. This paper examines three main cases with examples and \u0026nbsp;shows where recursion controls, terms raise similarly, or non-recursive work succeeds. Practical examples such as Binary Search, Merge Sort, Strassen's Matrix Multiplication etc are analyzed both through traditional Master Theorem classification and graph-based visual modeling, providing clearer insight into their asymptotic behaviors. This combined approach streamlines the classification process, highlights dominance patterns more intuitively, and offers a new perspective on recurrence analysis in modern computational problems.\u003c/p\u003e","manuscriptTitle":"Analysis of Recursive and Non-Recursive Complexity with Graph-Based Modeling","msid":"","msnumber":"","nonDraftVersions":[{"code":1,"date":"2025-10-21 04:09:16","doi":"10.21203/rs.3.rs-7893355/v1","editorialEvents":[{"type":"communityComments","content":0}],"status":"published","journal":{"display":true,"email":"[email protected]","identity":"researchsquare","isNatureJournal":false,"hasQc":true,"allowDirectSubmit":true,"externalIdentity":"","sideBox":"","snPcode":"","submissionUrl":"/submission","title":"Research Square","twitterHandle":"researchsquare","acdcEnabled":true,"dfaEnabled":false,"editorialSystem":"","reportingPortfolio":"","inReviewEnabled":false,"inReviewRevisionsEnabled":true}}],"origin":"","ownerIdentity":"10bdc1dc-6596-480b-b888-a95d6b2beea8","owner":[],"postedDate":"October 21st, 2025","published":true,"recentEditorialEvents":[],"rejectedJournal":[],"revision":"","amendment":"","status":"posted","subjectAreas":[{"id":56519793,"name":"Computer Architecture and Engineering"}],"tags":[],"updatedAt":"2025-10-21T04:09:16+00:00","versionOfRecord":[],"versionCreatedAt":"2025-10-21 04:09:16","video":"","vorDoi":"","vorDoiUrl":"","workflowStages":[]},"version":"v1","identity":"rs-7893355","journalConfig":"researchsquare"},"__N_SSP":true},"page":"/article/[identity]/[[...version]]","query":{"redirect":"/article/rs-7893355","identity":"rs-7893355","version":["v1"]},"buildId":"8U1c8b4HqxoKbykW_rLl7","isFallback":false,"isExperimentalCompile":false,"dynamicIds":[84888],"gssp":true,"scriptLoader":[]}