Below a formal method to deduce the order of growth of both your algorithms (I hope you're comfortable with Sigma Notation):
Calculating Time Complexity (2 Simple Algorithms)
-
15-06-2023 - |
Pergunta
Here are two algorithms (pseudo-code):
Alg1(n)
1. int x = n
2. int a = 0
3. while(x > 1) do
3.1. for i = 1 to x do
3.1.1 a = a + 1
3.2 x = x - n/5
Alg2(n)
1. int x = n
2. int a = 0
3. while(x > 1) do
3.1. for i = 1 to x do
3.1.1 a = a + 1
3.2 x = x/5
The difference is on line 3.2.
Time complexity:
- Alg1: c + c +n*n*2c = 2c + 2cn² = 2c(n² + 1) = O(n²)
- Alg2: c + c +n*n*2c = 2c + 2cn² = 2c(n² + 1) = O(n²)
I wanted to know if the calculation is correct.
Thanks!
Solução 2
Outras dicas
No, I'm afraid you aren't correct.
In the first algorithm, the line:
x = x - n/5
Makes the while
loop O(1)
- it will run five times, however large n
is. The for
loop is O(N)
, so it's O(N)
overall.
In algorithm 2, by contrast, x
decreases as
x = x/5
As x = n
to start with, this while
loop runs in O(logN)
. However, the inner for
loop also reduces as logN
each time. Therefore you are carrying out n + n/5 + n/25 + ...
operations, for O(N)
again.
Algorithm 1 :
you decrease the value of x by 5
, so you do n + n-5 + n-10 +....
which is O(N^2)
Algorithm 2 :
you decrease the value of x by n/5
, so you do n + n/5 + n/25 +....
which is O(N logN)
see wikipedia for big-oh {O()} notation