Scribd
Upload
39 views3 pages

Time Complexity of While Loops

The document discusses time complexity analysis of while and for loops. It provides 6 examples of loops and analyzes their time complexities. The time complexities analyzed are: 1) O(n) 2) O(n) 3) O(n) 4) O(n) 5) O(n) max time complexity, O(1) min time complexity 6) O(1) best case, O(n) worst case

Uploaded by

Dawan Noid
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
39 views3 pages

Time Complexity of While Loops

The document discusses time complexity analysis of while and for loops. It provides 6 examples of loops and analyzes their time complexities. The time complexities analyzed are: 1) O(n) 2) O(n) 3) O(n) 4) O(n) 5) O(n) max time complexity, O(1) min time complexity 6) O(1) best case, O(n) worst case

Uploaded by

Dawan Noid
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Time complexity

While loop

1. i =0 1
while (i<n) n+1
{statement ; n
i++; n
} 3n+2
F(n)= 3n+2
O(n)
OR
For(i=0; i<n;i++) O(n)
{ statement ;
}

2. a=1; there is no ‘n’ here


while (a<b)
{statement;
a=a*2;
}

A
1
1*2=2
2*2=4
22*2=23 ………..2k

This loop will terminate when a>=b


a=2k
2k >=b
K=𝑏
O(𝑛 )

OR

For (a=1; a<b;a=a*2)


3. i=n;
while (i>1)
{statement;
i=i/2;
} O(𝑛 )

OR
For(i=n; i>1; i=i/2)
4. i=1;
k=1;
while(k<n)
{statement;
K=k+i;
i++;
}

Untill k is less than n this loop will continue otherwise it will terminate.
k>=n

M2+1/2 >=n

M2>=n

M2=n O( 𝑛)

M= 𝑛

For ( k=1; i=1;k<n ; i++)

{statement;

K=k+I;

5. While (m!=n)
{ If(m>n)
M=m-n;
Else
N=n-m;
}

m/2

O(n) max time complexity

O(1) min time complexity

6. Algorithm test (n)


{if (n<5)

{printf(“%d”,n); 1 O(1) best case for this algo

Else

{for (i=0; i<n; i++)

{printf (“%d”, i); n O(n) worst case for this algo

You might also like