Abstract - Complexity of a program helps us to estimate the amount of work required for program development and its testing. To control complexity, one must be able to measure it. Researchers have proposed a wide range of complexity metrics. Some complexity measures which have been successfully transitioned into practice are Source Lines of Code (SLOC), Halstead Metrics and McCabe's Cyclomatic Complexity metric. These measures are based

on static paths in the control flow graph. Over here, we study a new measure called "Path Complexity" that computes the complexity of a program on the basis of distinct number of execution paths for an input of size n. We worked on the path complexity of the following

algorithms: KMP and Boyer Moore algorithm for pattern matching and the Strongly Connected Components algorithm.

I. INTRODUCTION

High software costs and the fact that more than 65% of the software life-cycle time is spent on testing and maintenance has created a considerable attention to the software complexity

problem. Over the last decade many software complexity measures have been proposed by researchers. These measures are being used for analyzing software complexity, software

understandability, software m odifiability, software testability, software maintenance and for software development. Our central goal here is to critically evaluate existing software complexity measures and to study the new complexity measure called the Path Complexity.

Measures of program complexity are seen as the best indicator of error-proneness or the likelihood of a piece of software to have an operational fault. The suggestion is that as the structure of the code becomes more complex, the programmer loses track of how one piece of code is affected by another and so even minor changes to the software can produce

unexpected results. It is on this basis that controlling the complexity of a program has a direct bearing on the quality of the overall system. Losing track of the structure of a system has been given as one reason why complex (often safety-critical) systems can never be deemed to be entirely safe.

We are trying to build up an effective complexity measure that takes into account all the parameters that adds to the complexity of a program and at the same time discards those parameters that are redundant and are unnecessarily added during the measurement of the complexity of a program.

II. EXISTING MEASURES

A. Source Lines of Code Source lines of code (SLOC) is software metric used to measure the size of a software program by counting the number of lines in the text of the program's source code. SLOC is typically used to predict the amount of effort that will be required to develop a program, as well as to estimate programming productivity or effort once the software is produced