calculate time complexity of nested for loops

Question

I am having trouble calculating the time complexity for these for loops:

for(int i=0; i<len; i++){
    countOne++;
    for(int j=i/2; j<len; j++){
        countTwo++;
        for(int k=i/2; k<len; k++){
            countThree++;
        }
    }
}

I don't understand how to calculate the time complexity for the 2 inner-most loops.

What, precisely, do you mean by "calculate the running time"? — David Schwartz
– David Schwartz, Commented Oct 13, 2013 at 5:27
yes, Big O running time. I would like to know the running time of each line, specifically the 2 inner loops. For example, I believe the first for loop runs n+1 times. — Adrienne Keck
– Adrienne Keck, Commented Oct 13, 2013 at 5:41
@AdrienneKeck I think the term you are looking for is time complexity, not running time (which is most commonly referred to as run time). It's impossible to calculate the run time of your code since this depends on an infinitely large number of additional factors. — Shashank
– Shashank, Commented Oct 13, 2013 at 6:22

Adam · Accepted Answer · 2013-10-13 06:16:32Z

3

This sounds like a Big Oh question. But you should specify that in the future.

countOne is incremented len times.
For every i, countTwo is incremented len-i/2 times. i goes from 0 to len-1, so countTwo is incremented between len/2 and len (or O(len)) times per i, or O(len²) in total.
similar story for countThree, it's incremented O(len³) times.

Therefore the entire algorithm is O(len³).

edited Oct 13, 2013 at 6:16

answered Oct 13, 2013 at 5:47

Adam

17.4k8 gold badges55 silver badges103 bronze badges

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

Comments

Mohamed Ennahdi El Idrissi · Accepted Answer · 2014-07-02 00:57:10Z

0

You proceed methodically with Sigma notation:

enter image description here

answered Jul 2, 2014 at 0:57

Mohamed Ennahdi El Idrissi

2,9872 gold badges21 silver badges35 bronze badges

Collectives™ on Stack Overflow

calculate time complexity of nested for loops

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related