Calculating Time Complexity (2 Simple Algorithms)

Question

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!

Answer 1

Below a formal method to deduce the order of growth of both your algorithms (I hope you're comfortable with Sigma Notation):

Answer 2

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.

Answer 3

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