Computer Science, asked by Umapathi8140, 1 year ago

How to find time complexity of algorithm?

Answers

Answered by anupambd94
1
If there is a single iteration, and the iterative variable is incrementing linearly then it's O(n) e.g.
for(i=0;i<n;i++) //O(n) 

for(i=0;i<n;i = i + 4) // still O(n)

If the iterative variable is incremented geometrically, then it's O(log n)
e.g
for(i=1;i<n;i = i * 2) //O(log n)

Note that, the implementations don't have to be using loops, they maybe implemented using recursion.

If there is nested loop, where one has a complexity of O(n) and the other O(logn), then overall complexity is O(nlogn);
e.g
for(i=0;i<n;i++) // O(n) 
{
   for(j=1;j<n;j=j*3) // O(log n) 
}
//Overall O(nlogn)

This is only a finger cross guideline. In general, you have to have a good concept to derive the complexity. 
Answered by Anonymous
0

Explanation:

Answer:

In several scientific fields, "complexity" has a precise meaning: ... It allows one to deduce many properties of concrete computational complexity measures, such as time complexity or space complexity, from properties of axiomatically defined measures.

Similar questions
Math, 8 months ago