Sign In
Create Account
Follow Us on Twitter
Subscribe on Youtube
I'd like to know how to determine the complexity of a program(both time and space)in C language.
I know a bit of theory,but still I am not sure to do things properly...
I think there are some ways,but I need the asymptotic method.
I would be happy If you can link me some good and simple tutorials to pratice with or show me some short code examples.
Thanks in advance.
1 reply to this topic
Back to top|
|
|
#2
Posted 07 January 2009 - 08:21 AM
WingedPanther
-
- Moderators
-
- 16,831 posts
A spammer's worst nightmare
Computing program complexity is not, in general, simple. For example, Quicksort's time complexity averages O(n log(n)) but has a worst case scenario of O(n^2). Also note that the language doesn't affect the complexity, but using a library function may have a hidden complexity cost.
For a gross generalizition, a loop has complexity O(n), a nested loop has O(n^nesting level), recursion can easily vary from O(log(n)) to O(n^2) to O(n!). I have created "simple" code with a single while loop that I estimated at time complexity O(((n!)!)!).
The only way to determine the complexity of a program is to understand what it is doing. You may want to do some profiling of different cases to help you with that process.
For a gross generalizition, a loop has complexity O(n), a nested loop has O(n^nesting level), recursion can easily vary from O(log(n)) to O(n^2) to O(n!). I have created "simple" code with a single while loop that I estimated at time complexity O(((n!)!)!).
The only way to determine the complexity of a program is to understand what it is doing. You may want to do some profiling of different cases to help you with that process.
