How to find time complexity of algorithm?
Answers
Answered by
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.
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
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
Computer Science,
8 months ago
Math,
8 months ago
Chemistry,
1 year ago
Chemistry,
1 year ago
Chemistry,
1 year ago