electrofriends.com > Questions > Algorithm time complexity, for loop > Calculating Algorithm time complexity

Calculating Algorithm time complexity

0

How to calculate Algorithm time complexity about for loop?and the other?

Tags: asked May 29, 2012
Avatar Image
Maple Zhou
0

1 Answer

1

Complexity of the loop is "On the Order of N" time, or O(N), because it is Linear. Run time varies directly with N.

For example, let us assume that any single statement takes a constant amount of time, T. So if your statement is

i = 3;

the time it takes to run is T.

Now suppose you have a loop that runs N times:

for (int i = 0; i<N; i++)
{
i = 3;
}

It will take N*C, since you're doing a statement that takes T time, N times.

Suppose you have two loops:

for (int i = 0; i<N; i++)
for (int j = 0; j<N; j++)
i = 3;

Now you're running the statement N*N times, so the complexity of this code is O(N^2).

Other imaginable sequences could take sqrt(N) time. We say this are O(log N).

Avatar Image
chitra
35

Your Answer

Please login to post questions.

Question and Answer
C/C++ Unix & Linux Wordpress
Source codes
C C++ Java

Free email signup

Email: