Cyclomatic complexity is a software metric that measure the logical strength of the program. It was developed by Thomas J. McCabe. Cyclomatic complexity is calculated by using the control flow graph of the program. In the flow graph, nodes are represented by circle. Areas bounded by edges and nodes are called regions. When counting regions, we also include the area outside the graph as a region.

Complexity is computed in one of three ways:

The total number of regions of the flow graph.

By using the formula defined as:

V(G) = E - N + 2

Cyclomatic complexity, V(G), for a flow graph, G, is also defined as

V(G) = P + 1 ,where P is the number of predicate nodes contained in the flow graph G.

Note: Nodes that contain a condition is called a predicate node and is characterized by two or more edges originating from it.

Learn more »

In computer science, the prefix sum, scan, or cumulative sum of a sequence of numbers x₀, x₁, x₂, ... is a second sequence of numbers y₀, y₁, y₂, ..., the sums of prefixes (running totals) of the input sequence:

y₀ = x₀

y₁ = x₀ + x₁

y₂ = x₀ + x₁+ x₂

...

For instance, the prefix sums of the natural numbers are the triangular numbers:

input numbers	1	2	3	4	5	6	...
prefix sums	1	3	6	10	15	21	...

This problem can be solved by using divide and conquer method. The pseudo-code for this is given below:

1. if (n==1) do nothing and return
2. Do in parallel
1. make recursive call for prefix_compute(A[1], A[n/2])
2. Make recursive call for prefix_computer(A[n/2+1],A[n])
3. for each A[n/2+1] do A[i] = A[i] + A[n/2]

Here, Step 1 takes O(1) and Step 2 takes T(n/2) since two recursive calls are made to two subsets. Also, in step 3, second half of the processor, i.e. subset 2 reads the global value of A[n/2] concurrently and update their answer. This takes O(1).

Hence, Time complexity is given by T(n) = T(n/2) + O(1). Solving this my Master theorem method, we have,

T(n) = T(n / 2) + O(1)

Since the Master Theorem works with recurrences of the form

T(n) = aT(n / b) + n^c

In this case you have

• a = 1
• b = 2
• c = 0

Since c = log_ba (since 0 = log₂ 1), you are in case two of  the Master Theorem, which solves to Θ(n^c log n) = Θ(n⁰ log n) = Θ(log n).

Learn more »

1. A Θ( n ) algorithm is O( n )
2. A Θ( n ) algorithm is O( n² )
3. A Θ( n² ) algorithm is O( n³ )
4. A Θ( n ) algorithm is O( 1 )
5. A O( 1 ) algorithm is Θ( 1 )
6. A O( n ) algorithm is Θ( 1 )

Solution

1. We know that this is true as our original program was Θ( n ). We can achieve O( n ) without altering our program at all.
2. As n² is worse than n, this is true.
3. As n³ is worse than n², this is true.
4. As 1 is not worse than n, this is false. If a program takes n instructions asymptotically (a linear number of instructions), we can't make it worse and have it take only 1 instruction asymptotically (a constant number of instructions).
5. This is true as the two complexities are the same.
6. This may or may not be true depending on the algorithm. In the general case it's false. If an algorithm is Θ( 1 ), then it certainly is O( n ). But if it's O( n ) then it may not be Θ( 1 ). For example, a Θ( n ) algorithm is O( n ) but not Θ( 1 ).

Learn more »

NO, It can not solve all the problems.

For example, Turing Machine can not solve Halting problem.

Learn more »

Here, using binomial theorem for expanding (n+a)^b, we get,
C(b,0)n^b+C(b,1)n^(b-1)a+.....+C(b,b-1)na^(b-1)+C(b,b)a^b
We can obtain some constants such that (n+a)^b<=c1*(n^b), for all n>=n0
and (n+a)^b >=c2*(n^b), for all n>=n0

Here we may take c1=2^b, c2=1, n0=|a|
Since, 1*(n^b)<=(n+a)^b<=2^b*(nb)

Hence, the problem is solved. Learn more »

An algorithm is a finite set of computational instructions, each instruction can be executed in the finite time, to perform computation or problem solving by giving some value or a set of values as input to produce some value or a set of values as output.

Algorithm Properties

Input(s)/Output(s) : There must be some inputs from the standard set of inputs and an algorithm's execution must produce output(s)

Definiteness: Each step must be clear and unambiguous

Finiteness: Algorithms must terminate after finite time or steps.

Correctness: Correct set of output values must be produced from each set of inputs.

Effectiveness: Each step must be carried out in finite time.




Learn more »

This RAM model is the base model for our study of design and analysis of algorithms to have design and analysis in machine independent scenario. In this model, each basic operations like addition and subtraction takes 1 step, loops and subroutines are not basic operations. Each memory reference is 1 step. We measure run time of algorithm by counting the steps. Learn more »