C++

Forum

 
Run Time

darje (37)
is the running time of this algoritem..
is O(n)? how to calculate this?
i know is o(N)+O(10) +(O(5)*log(N) ?
can someone explain The correct answer and exaplain me please

1
2
3
4
5
6
7
 
 for (i = 1; i <= n; i++)
for (j = 1; j <= 10; j++)
for (k = n; k <= n+5; k++) {
 x = n;
 while (x > 1)
 { x = x / 2; S; }
 }
Peter87 (11226)
Think about how many times the innermost code x = x / 2; S; will run.

The outermost for loop (line 1) will repeat n times.
The intermediate for loop (line 2) will repeat 10 times in each iteration of the outermost for loop.
The innermost for loop (line 3) will repeat 6 times in each iteration of the intermediate for loop.
The while loop (line 5) will repeat approximately log₂(n) times in each iteration of the innermost for loop.
So in order to get the total number of times that line 6 will be repeated you need to multiply all of these numbers.
n × 10 × 6 × log₂(n) = 60 × n × log₂(n)

When dealing with time complexities we are not interested in constants so 60 is simply ignored.
The conclusion is that the algorithm is O(n × log(n)).
Last edited on
darje (37)
hey peter tnx for responding.

why you mulitply evrything even the most outer loops?
the most inner for loop isnt inside the outer loop ,,
so isnt suppost to be

o(n) + o(10) +(o(5)* log(n)) = O(n)?

beacuse o(N)> log(n) =so its o(n) ?

lets say i have the same method with like this,,
1
2
3
4
5
6
7
8
9
10
11
12
13
 
 
 for(i = 1; i <= n; i++){
something3:
}
for (j = 1; j <= 10; j++){
someting;
}
for (k = n; k <= n+5; k++) {

 x = n;
 while (x > 1)
 { x = x / 2; S; }
 }


its still the same run time?
Last edited on
Peter87 (11226)
I just assumed the code followed the rules of C and C++ in which case the second loop would be inside the first loop, the third loop inside the second loop, and so on.

1
2
3
4
5
6
7
8
9
10
11
 
for (i = 1; i <= n; i++) {
	for (j = 1; j <= 10; j++) {
		for (k = n; k <= n+5; k++) {
			x = n;
			while (x > 1) { 
				x = x / 2; 
				S; 
			}
		}
	}
}


If the code is indeed meant to be interpreted as two separate for loops followed by a for loop with a while loop inside, like in your second post, then it is correct to conclude that it is O(n) because we only care about the biggest factor.

O(n + 10 + 6×log(n)) = O(n)
Last edited on
darje (37)
tnx you very much peter87 ! you really helpd me alot <:
Topic archived. No new replies allowed.