class test

Question

m=1;

for i=1 to n do begin

        m=m*3;

        for j=1 to m do

               {Something which is O(1)}

What is the complexity of above algorithm?

1. O(n*m3)

2. O(n3)

3. O(3n)

4. O(3m)

Comments

it will be O(3ⁿ)

3 + 3² + 3³ + 3⁴........3ⁿ = O(3ⁿ)

Answer 1

Outer Loop Run                  Inner Loop Run

  i=1, m=3                       j=(1 to 3)  i.e Total 3 times

i=2, m=3^2                    j=(1 to 3)  i.e Total 3^2 times

i=3, m=3^3                    j=(1 to 3^3)  i.e Total 3^3 times

                         .

                         .

i=n, m=3^n                    j=(1 to 3^n)  i.e Total 3^n times

Total Number of times loop executes = 3+ 3^2+ 3^3 + 3^4 ......+3^n

                                                    =3(3^n-1)/(3-1)

                                                    =O(3^n)

Answer 2

option C

Comments

okk sir.

---

How 'm' is constant? After the successful execution of the program m will become $3^n$.

So option 1, 3, 4 all are correct. Only 2nd option is false.

Option 1, 3, 4 all provide the upper bound on the time complexity of the program. So all are valid.

1. O(n*$m^3$) = O( n * $3^n^3$. which is asymptotically greater than $3^n$. So it is also the correct option.

4. O($3^m$) it is also asymptotically greater than $3^n$.

---

@Hemant

why are you taking final value of m i.e m=3ⁿ? why not initial value i.e m=1?

i think above qsn will proof why can't comlexity be O(3^m)

one more claim, suppose you say complexity of above code -> O(3^m), is it correct??...no, because if i say initially m=2 or 3 or 100 etc etc, then program must run in constant time, but see, it is still taking O(3ⁿ) time.

hope you got now!

Answer 3

Option C is correct.

The complexity depends upon how many times the innermost loop run in this case

Just dry run the program using initial values and we can observe the pattern formed and can be calculated easily.

Sorry for handwriting and clarity :)

Hope it helps :)