What is the complexity of the following C code segment Show

What is the complexity of the following C++ code segment? (Show your work.) void UnsortedType: Deleteltem(int a. float b) {a = a/3; b = a; for (int is 0; i

Solution

1)-Void UnsortedType::DeleteItem(int a,float b)------------------Constant time O(1)

2)-{----------------------------------------------------------------------- Constant time O(1)

3)-a =a/3; --------------------------------------------------------------- Constant time O(1)

4)-b= a;------------------------------------------------------------------ Constant time O(1)

5)-for(int i=0;i<n;i++)-----------------------------------------------------------------O(n)

6)-{---------------------------------------------------------------------------------------O(n)

7)-for(int j=1;i<n;i++)----------------------------------------------------------- O(n)*O(n)

8)-     {-------------------------------------------------------------------------- O(n)*O(n)

9)-               a = a*2;----------------------------------------------------------- O(n)*O(n)

10)-   }--------------------------------------------------------------------------- O(n)*O(n)

11)-} ---------------------------------------------------------------------------------------O(n)

12)-If(b>0)-------------------------------------------------------------- Constant time O(1)

13)-b =100; ------------------------------------------------------------- Constant time O(1)

14)-} --------------------------------------------------------------------- Constant time O(1)

Now We Analysis the code line by line

Line number 1)- constant time Because it’s executed only ones when the caller method is called this code.

Line number 2 - to Line number 4 Code is executed by Only Once time because when first time the function is called initialization and deviation process is work

Line number 5 –the Loop is executed n times so the Complexity will be O(n)

Line number 6- this is simple braces code we can’t count it for Complexity , but for kind consideration this will also executed O(n) time.

Line number 7- the Loop is executed n times so the Complexity will be O(n)

     But this Loop is depend upon outer Loop Means for every value of (i) the inner loop will be executed n times. The complexity will be

  When i=0 the loop will be executed n times

When i=1 the loop will be executed n times

When i=2 the loop will be executed n times

.         .         .         .         .         .         .

.         .         .         .         .         .         .

.         .         .         .         .         .         .

When i=n-2 the loop will be executed n times

When i=n-1 the loop will be executed n times

So the total time for inner Loop Execution will be O(n)*O(n)=O(n²)

The same process with happen for Line number 8 and 9 and 10.

Line number 11 will be executed O (n) Time because it is associated with Outer Loop.

Line number 12, 13 and 14 will be executed only Once.

But we for Complexity counting we fallow some rule

i)- take only loop’s and expression

ii)- Only Maximum Complexity of the Code

so Line number7, 8 and 9 and 10 have Same Complexity = O(n²)

So the Overall Complexity Will be              O(n²).