By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
454,470 Members | 1,482 Online
Bytes IT Community
+ Ask a Question
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<iostream>
#include<stdlib.h>
using namespace std;

int main(){
int i, j, n;
for(i=0;i<n; i++){

for(j=0; j<n; j++){
cout<<"my time complexity is = "<<i*j<<endl;
}
cout<<"complexity is increasing"<<j<<endl;
}
system("pause");
return 0;
}
Nov 8 '08 #1
Share this Question
Share on Google+
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

Ganon11
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
  1. for (int i = myList.size(); i > 0; i/=2) {
  2.    // ...
  3. }
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
  1. for (int i = myList.size(); i >= 0; i/=2) {
  2.    // ...
  3. }
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

Ganon11
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

Ganon11
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

Post your reply

Sign in to post your reply or Sign up for a free account.