GATE IT 2006 | Question: 16

Question

The cyclomatic complexity of the flow graph of a program provides

• A. an upper bound for the number of tests that must be conducted to ensure that all statements have been executed at most once
• B. a lower bound for the number of tests that must be conducted to ensure that all statements have been executed at most once

• C. an upper bound for the number of tests that must be conducted to ensure that all statements have been executed at least once

• D. a lower bound for the number of tests that must be conducted to ensure that all statements have been executed at least once

Answer 1

its C as each edge must be visited at least once that's why we use cyclomatic complexity to determine the number of independent paths.

Comments

But why is it an upper bound?

---

http://users.csc.calpoly.edu/~jdalbey/206/Lectures/BasisPathTutorial/

supports the answer C

---

Arjun Sir... Please Clarify... Thank you!!

---

Cyclomatic complexity provides an upper bound for the number of test cases needed to ensure all program statements are covered.

It is also a lower bound to the number of paths in the control flow graph. (not independent paths).

https://en.wikipedia.org/wiki/Cyclomatic_complexity

Answer 2

Ans C)

---

The value for V(G) provides us with an upper bound for the number of independent paths that form the basis set ( a set of independent paths for the flow graph such that if tests can be designed to force execution of these paths then every statement in the program will have been guaranteed to be executed at least one time and
every condition will have been executed on its true and false sides) and, by implication, an upper bound on the number of tests that must be designed and executed to guarantee coverage of all program statements.

Thus, Cyclomatic complexity, V(G), for a flow graph, G, is defined as
V(G) = E - N + 2
Also, it can be defined as
V(G) = P + 1,

where P is the number of predicate nodes contained in the flow graph G. ( A predicate node is a node containing a condition.)