Time complexity of loops

[aishaahmad]

Hi,
I am a newbie. I am studying Algorithms for the very first time in this semester, so please dont get annoyed by my question.

The time complexity of the loop e.g for(int i=0;i<N;i++) is O(N). Now what would be the time complexity of the loop that isnt incremented by one.
eg

int i=1;
while(i<N)
{
	for(int j=1; j<N; j *= 5)
	{
		for(int k=0;k<N;k++)
		 cout<<”Complexity Analysis”;
	}
	i=i*3;
}

[darkagn]

Hi there aishaahmad and welcome to Daniweb,

Sorry but we aren't allowed to just do your homework for you. Do you know what is meant by O(N) and why that loop is O(N)? Do you understand what the term time complexity means?

Also, you have two loops that don't increment by one...

[aishaahmad]

Hi
All I know is that running time of an algorithm is usually measured as function of input size. since usually time grows with size of input, and running time is measured by number of steps operations performed.
complexity of the loop is O(N), because it is Linear. run time varies directly with n.

I wanted to know the complexity of the loops that are not incremented by one. Okey forget about the above code. Just let me know the time complexity of the following type of loop :
for(int j=1; j<N; j *= 5)

Thanks in advance.

[darkagn]

How do you think the "j *= 5" part of the for loop affects the number of operations performed as the input size (n) gets very large?

[aishaahmad]

I am just saying that the loop wont execute N times. since each time it is incremented by j*5

okey fine, you should have mentioned at the very start that you dont want to answer.
Bye :(

[darkagn]

I am just saying that the loop wont execute N times. since each time it is incremented by j*5

okey fine, you should have mentioned at the very start that you dont want to answer.
Bye :(

Actually I am trying to help you discover the answer without just giving it to you.

How do you think the "j *= 5" part of the for loop affects the number of operations performed as the input size (n) gets very large?

This question was a bit misleading sorry.

What I meant was, how does the "j *= 5" part of the loop affect the way that the number of iterations grows as n gets large? Start with n=1, how many times does this loop iterate? Now try n=20, n=100, n=10000? Do you see some sort of pattern? Is it growing linearly or quadratically? Or something else?

[nitin.infoit]

Hi,

I need to calculate the time complexity of the following code:

cost frequency
1. for i <- 1 to n c1 n+1
2. do for j <- 1 to i c2 n(n+1)/2
3. do for k <- 1 to j c3 ?
4. do count<- count + 2 c4 ?
5. retrun c5 1

i want to know the time complexity in 3rd step & 4th step....so plz tell me with some explanation....

i only know that the running time of this algorithm is O(n^4).

[AuburnMathTutor]

c3: will do (j+1) assignments (i) times. Therefore you only need to solve the double summation (sum of i from 1 to n of (sum of j from 1 to i of ((j+1)i)).

c4: will do j additions by two and j assignments. Therefore you only need to solve the double summation (sum of i from 1 to n of (sum of j from 1 to i of (2j)).

To solve a double summation, solve the inner summation first, treating the outer summation variable(s) as constant, and work your way inside out until all variables are gone and you have a closed form solution with no summations.

Hope this helps.