Time Complexity : The time complexity of a problem is the number of steps that it takes to solve an instance of the problem as a function of the size of the input (usually measured in bits), using the most efficient algorithm.
So we denote it in form of o(n) notation. [There are different notations for best , average, worst case (symboled by theta, omega and bit O)]. Generally a time complexity will be the time required for the most time consuming activity of algorithm.
e.g.
CODE
void print()
{
for(int i=0;i<n,i++)
{
printf("%d ",i);
}
for(int j=0;j<n,j++)
{
for(int i=0;i<n,i++)
{
printf("%d ",i*j);
}
}
}
This will have time complexity of O(n^2) and the nested for loop will be the time consuming activity in any case.
In general calculation of time complexity of algorithms can be done using following calculations...
return 0; - statement like this executes in defined time [say 1 unit] so it's time complexity will be constant.
for ( i = 0; i < N; i++ ) printf("a"); - this for loop will take n iterations to finish, so total statement executions will be 3N+1, as this is directly proportional to N the time complexity here will be O(n).
you already have one example of O(n^2) above.
CODE
while ( low <= high ) {
mid = ( low + high ) / 2;
if ( target < list[mid] )
high = mid - 1;
else if ( target > list[mid] )
low = mid + 1;
else break;
}
This code uses divide and conquer strategy, which makes it logarithmic i.e. The running time of the algorithm is proportional to the number of times N can be divided by 2. so it's complexity will be O(log n).
There are complexities like O(n^3), O(n*log n) etc. You can explore about them by yourself.
This and
this can be a good resource on it.
Space Complexity : The space complexity of a problem is a related concept that measures the amount of space or memory required by the algorithm. An informal analogy would be the amount of scratch paper needed while working out a problem with pen and paper.
So similar to time complexity, this also considers the highest memory consuming part of the code as the decider of space complexity.
This can be a good resource on it.
This post has been edited by AmitTheInfinity: 7 Jan, 2009 - 05:23 AM
Forum Index:
Programming Help |
C and C++ |
VB6 |
Java |
VB.NET |
C# |
ASP.NET |
PHP |
ColdFusion |
Perl and Python |
Ruby |
Databases |
Other Languages |
Game Programming |
Mobile Development |
Software Development |
Computer Science |
Industry News |
Programming Tutorials |
C++ Tutorials |
Visual Basic Tutorials |
Java Tutorials |
VB.NET Tutorials |
C# Tutorials |
Linux Tutorials |
PHP Tutorials |
ColdFusion Tutorials |
Windows Tutorials |
HTML/JavaScript Tutorials |
CSS Tutorials |
Flash Tutorials |
Web Promotion Tutorials |
Graphic Design & Photoshop Tutorials |
Software Development Tutorials |
Database Tutorials |
Other Language Tutorials |
ASP.NET Tutorials |
Game Programming Tutorials |
WPF & Silverlight Tutorials |
7 Jan, 2009 - 04:25 AM
| 
