Scribd
Upload
6 views2 pages

Time Complexity Analysis of Algorithms

The document outlines the time complexity analysis for six different algorithms. The complexities range from O(log2 n) for logarithmic growth to O(√n) for algorithms with quadratic conditions, and O(n) for a simple summation algorithm. Additionally, space complexity is noted for one algorithm as O(1).

Uploaded by

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

Time Complexity Analysis of Algorithms

The document outlines the time complexity analysis for six different algorithms. The complexities range from O(log2 n) for logarithmic growth to O(√n) for algorithms with quadratic conditions, and O(n) for a simple summation algorithm. Additionally, space complexity is noted for one algorithm as O(1).

Uploaded by

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

Find time complexity for the following algorithms/programs

1. for(i=n; i>=1; i=i/2)


{
Statement;
}

Solution: i = n, n/2, n/22, n/23……n/2k


Assume i<1 for kth iteration (Stopping condition)
n/2k <1 => n/2k =1 => n = 2k => k = log2 n
Time Complexity = O( log2 n)

2. for(i=0; i*i <n; i++)


{
Statement;
}

Solution: Here condition is i*i <n


Assume i2>n (Stopping condition)
i2=n => i=√n
Time Complexity = O(√n)

3. a=1;
while(a<b)
{
Statement;
a=a*2;
}
Time Complexity = O( log2 b)

4. i=n;
while(i>1)
{
Statement;
i=i/2;
}
Time Complexity = O( log2 n)

5. i=1;
k=1;
while(k<n)
{
Statement;
k=k+i;
i++;
}
Time Complexity = O(√n)

6. Algorithm Total(n)
{
i=0;
total=0;
for(i=1;i<=n;i++)
{
total=total+i;
}
return 0;
}

Time Complexity = O(n) {2n+4}


Space Complexity = O(1) {3 words}

You might also like