| dc.contributor.advisor | Amin, Ashok T. | |
| dc.contributor.author | Mangal, Anupam | |
| dc.date.accessioned | 2017-06-10T14:37:07Z | |
| dc.date.available | 2017-06-10T14:37:07Z | |
| dc.date.issued | 2007 | |
| dc.identifier.citation | Mangal, Anupam (2007). On path complexities of heapsort algorithm and the class stack. Dhirubhai Ambani Institute of Information and Communication Technology, ix, 49 p. (Acc.No: T00105) | |
| dc.identifier.uri | http://drsr.daiict.ac.in/handle/123456789/142 | |
| dc.description.abstract | A measure of program complexity, called Path Complexity, based on the number of program execution paths as a function of the input size n, is proposed in [AJ05]. This measure can be used to compare the complexity of two different programs even with isomorphic control flow graphs. Using this measure, we determine the path complexity of the Heapsort algorithm. The notion of path complexity of a program is further extended to introduce the path complexity of a class. In particular, the path complexity of the Stack class is determined. We also provide an upper bound, and a lower bound based on catalan numbers, on the path complexity of the Stack class. | |
| dc.publisher | Dhirubhai Ambani Institute of Information and Communication Technology | |
| dc.subject | Complexity theory | |
| dc.subject | Computational complexity | |
| dc.subject | Algorithms | |
| dc.subject | Paths and cycles | |
| dc.subject | Graph theory | |
| dc.subject | Graph theory | |
| dc.subject | Path analysis | |
| dc.subject | Heapsort | |
| dc.classification.ddc | 515.9 MAN | |
| dc.title | On path complexities of heapsort algorithm and the class stack | |
| dc.type | Dissertation | |
| dc.degree | M. Tech | |
| dc.student.id | 200511003 | |
| dc.accession.number | T00105 | |
