Determining big-O of a given algorithm

Question

I am given this algorithm (pseudo code, not in any specific language):

foo1(l,m,n){
    for ( i = 1; i < l, i++){
        for( j = 1; j < m ; j++){
            for ( k = 1; k < n; k++){
            //Constant time inner loop
            }
        }
    }
}

I am trying to find the number of times he inner loop runs in respect to l, m, and n and come up with a function for it. I also am trying to figure out the big-O notation for the algorithm.

Looking at the algorithm, I was thinking that the inner loop would run l*m*n times. I came up with this because for example, if l,m,n were 3, 6, 9 respectively, then the inner loop would run(9*6*3) times. So the function that would return the number of times the inner loop runs would be something like:

f = l*m*n

Now the big-O is where I am struggling with (not necessarily with this problem) but I wanted to get some further insight as so how to tackle big-O problems to best determine the right big-O for an algorithm.

For this specific case, I was thinking that the big-O would be n^3 but that is just based on a guess really. How do I go about figuring out what the big-O actually is for this problem, and more generally for other algorithms I may encounter?

It would be O(l*m*n). If there were constraints on the values of `l` and `m` that made them asymptotically equal to `n`, then it would be possible to simplify it to O(n^3). — Ted Hopp, Sep 29 '14 at 16:22
Since it seems you want to know all about `big-o` notation, and not any particular problem, I think the question is too big to fit SO. Voting to close. — axiom, Sep 29 '14 at 17:06

score 1 · Accepted Answer · edited May 23 '17 at 12:27

You are on the right track of understanding big-O. Above pseudo code indeed has complexity of O( lmn ) As you are probably looking for some references, I would like that you have a look at the following awesome post on stack overflow itself:

Plain English explanation of Big-O

In my opinion,this is one of the best guide to get you started with Big-O concepts.

If you delve further into depth follow this MIT Lecture .This will surely give you a nice ride about Big-O concepts in detail. I think these two references will clear lot of your concepts and will definitely help building your solid understanding.

Happy Leaning!

Determining big-O of a given algorithm

1 Answers1