for ( i = 0; i <= n; i = i +2 )
for ( j = n; j >= i; j - - )
I know the outer loop runs for n/2 + 1 times
i cant figure out how many times would the inner loop runs
if we assume n = 10
the inner loop runs for 10 times when i = 0
the inner loop runs for 8 times when i = 2
and so on but i cant figure out what time complexity would that be?
Let us assume an arbitrary
n
and consider ani
such that0 <= i <= n
. You're right in saying that the outer loop will run forn/2+1
times.Let's see how many times the inner loop will run for a given
n
andi
. The inner loop's j values go from i to n like thisSo basically the number of steps the inner loops takes is the number of terms in this sequence which if you look is
n-i+1
(you actually have an error in your question; ifn = 10
andi = 0
, the inner loop takes 11 steps not 10).So to get the total number of steps the two loops make, we need to
sum n-i+1 for i=0 to i<=n, i+=2
. LetS(n-i+1)
denote this sum. Then:Now
S(i) = 0 + 2 + 4 + ... + n
which is an arithmetic progression. The sum of this isn*(n/4+1/2)
thus our total sum isAnd so the dominant term is the
n^2
resulting in a complexity ofO(n^2)
.Looks like average number of iterations within inner loop is
n/2
. Then: