Simple Algorithm complexity

Question

I have an algorithm and I need help finding the complexity of it (tightest possible upper bound)

for(int i = 0; i < n/2; i++)
    for(int j = 0; j < n/4; j++)
        for(int k = 0; k < n; k++)
            x++;

My analysis is that if n would not be divided in each for loop, it would be O(n^3). This complexity still holds true, since each "for loop" will reduce each operation to a O(log n) complexity since it divides n every time the loop executes, making it smaller and smaller (smaller than O(n) at least).

I would say that the answer is between O(log n) and O(n^3). Could you help me getting the tightest possible bound?

n is never modified => complexity Θ(n * (n/4) * (n/2)) = Θ(n³) — fabian
– fabian, Commented May 12, 2015 at 11:34

Lrrr · Accepted Answer · 2015-05-12 11:36:20Z

3

start with inner loop :

for(int k = 0; k < n; k++)
    x++;

is obviously O(n).

now one layer above that :

for(int j = 0; j < n/4; j++)

is O(n) because it takes n/4 for j to reach the n and we know that O(n/4) = O(n)

and like this for outer loop is O(n).so the complexity is O(n^3) because you have three nested loop each with O(n) and non of them have effect on each other.

answered May 12, 2015 at 11:36

Lrrr

4,8055 gold badges44 silver badges65 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

idelara Over a year ago

Ok! So the tightest bound possible for this algorithm is indeed O(n^3) ?

Lucifer · Accepted Answer · 2015-05-12 12:32:07Z

3

Assume each step takes time C. For k-loop, time taken is Cn. For j-loop, time taken to complete iteration is (Cn)n/4=C(n^2)/4 For i-loop, time taken to complete iteration is (C*(n^2)/4)n/2=C(n^3)/8

So Total time taken=(C/8)*(n^3)

As C/8 is a constant it can be ignored when considering Big-O Notation. Thus, Time Complexity=O(n^3).

answered May 12, 2015 at 12:32

Lucifer

413 bronze badges

1 Comment

sair Over a year ago

my answer in words is urs

sair · Accepted Answer · 2015-05-12 12:12:35Z

2

for(int i = 0; i < n/2; i++)    --> n/2
    for(int j = 0; j < n/4; j++)  --> n/4
        for(int k = 0; k < n; k++)  --> n
            x++;

Hence total complexity is O((n^3)/8) which is O(n^3)

edited May 12, 2015 at 12:12

answered May 12, 2015 at 11:33

sair

8327 silver badges23 bronze badges

2 Comments

idelara Over a year ago

How do you get from O(n^3/8) to O(n^3)?

sair Over a year ago

8 is a constant , and can be ignored

Collectives™ on Stack Overflow

Simple Algorithm complexity

3 Answers 3

1 Comment

1 Comment

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

1 Comment

1 Comment

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related