CODEWITHSUNDEEP
timebig-otime-complexity
kofhearts
kofhearts

Reputation: 3774

What is the bigOh or running time of the following algorithm

What is the running time of the following algorithm in bigO.

for(int i=1;i<=n;i++){
    for(int j=i;j<=n;j++){
        for(int k=j; k<=n;k++){
            for(int l=k; l<=n;l++){

                ...

            }
        }
    }
}

Upvotes: 1

Views: 248

Answers (5)

Mohamed Ennahdi El Idrissi
Mohamed Ennahdi El Idrissi

Reputation: 2977

A formula for such a collection of dependent loops, can be inferred like the following:

enter image description here

Where c (constant) is the number of operations inside the innermost loop, n is the number of elements, and r is the number of nested loops.

In the question's case:

enter image description here

enter image description here

Another methodology, efficient but tedious, is to use Sigma notation:

enter image description here

Upvotes: 1

Mirza Shan
Mirza Shan

Reputation: 1

my answer is O(N^4)...because there are four "for loops"..and it is easy to judge the runing time of this algo...thanks !

Upvotes: 0

C0L.PAN1C
C0L.PAN1C

Reputation: 12243

O(N^4) is the cost.

each for nested is N^ so essentially N * N * N * N = N^4

CS610, Algorithm Development, NJIT. My graduate coursework is actually coming in handy.

Upvotes: 0

xpda
xpda

Reputation: 15813

N^4. The fractional part doesn't count.

Upvotes: 2

Dino
Dino

Reputation: 1576

This algorithm seems to be n^4. Of course, from the theoretical perspective (without any compiler considerations).

Upvotes: 7

Related Questions