454,470 Members | 1,482 Online
Need help? Post your question and get tips & solutions from a community of 454,470 IT Pros & Developers. It's quick & easy.

# how to calculate time comlexity of the given algorithm code

 P: 5 #include #include using namespace std; int main(){ int i, j, n; for(i=0;i
7 Replies

 Expert 10K+ P: 11,448 For any value of n >= 0 your outer loop body runs n times and your inner loop body runs n*n times so O(n^2) is the big-Oh value. kind regards, Jos Nov 8 '08 #2

 Expert 2.5K+ P: 3,652 Of course, if you put this code into your compiler and run it, you have no idea what will happen, since you never give a value to n. In general, most loops will have a complexity of O(n) where n is the difference between the initial value and the final value of the index. Most for loops start at 0 or 1 and end at some variable value like n, or size, or so on. Be careful, though, as some loops are tricky. The following loop, for example, is not O(n) but in fact O(log n): Expand|Select|Wrap|Line Numbers for (int i = myList.size(); i > 0; i/=2) {    // ... } Nov 8 '08 #3

 Expert 10K+ P: 11,448 Be careful, though, as some loops are tricky. The following loop, for example, is not O(n) but in fact O(log n): Expand|Select|Wrap|Line Numbers for (int i = myList.size(); i >= 0; i/=2) {    // ... } If there's no 'break' or 'return' in the body of that loop it actually is a 'dynamic halt', i.e. it never ends, it is O(infinity) ;-) kind regards, Jos Nov 8 '08 #4

 Expert 2.5K+ P: 3,652 Well, if you treat i as a floating point number - then it would eventually get to 0.5, 0.25, 0.125, 0.0625, etc... which is an infinite series converging to 0. However, because C/C++ get easily confused with floating points and ints, they say, "Meh, with ints, 1/2 is 0." Nov 8 '08 #5

 Expert 2.5K+ P: 3,652 Or I could realize that I said i >= 0, and 0/2 is 0... Nov 8 '08 #6

 Expert 10K+ P: 11,448 Or I could realize that I said i >= 0, and 0/2 is 0... :-) yep, that was what I was pointing at. kind regards, Jos Nov 8 '08 #7

 Expert 100+ P: 2,415 The OP didn't actually ask a question, except in the title of the post. By "time complexity" did you mean big-oh, such as O(n^2)? All of the replies were based on inspection of the source code; do you need to obtain an answer by executing the code? Nov 8 '08 #8