Well if you use a for loop to store an array that is O(N) and then if you use another for loop to loop through the array its another O(N) time. So O(N) + O(N) is O(2N). Now if you say this:
C = N
C' = 2 * N
C' is just an arbitrary constant of C. So from here you can say that its just O(C) where C is just a constant amount. So its still O(N).
for loop ------ help
Quote:Original post by LostSource
C' is just an arbitrary constant of C. So from here you can say that its just O(C) where C is just a constant amount. So its still O(N).
I'll take your word for it; I'm sure the time does increase at the same rate for any N. My point was using an array introduces unnecessary logic that only works to make the end-result less efficient and slow - instead of reading numbers, think about reading classes with expensive constructors/destructors/copies and assignments.
An interesting variation on this theme is:
You are given a list of integers, under the form of a function which returns the next integer when called, and a function which returns true if and only if there is a next integer. Can you compute the maximum element of the second half of the list in constant space?
You are given a list of integers, under the form of a function which returns the next integer when called, and a function which returns true if and only if there is a next integer. Can you compute the maximum element of the second half of the list in constant space?
Quote:Original post by stylinQuote:Original post by LostSource
C' is just an arbitrary constant of C. So from here you can say that its just O(C) where C is just a constant amount. So its still O(N).
I'll take your word for it; I'm sure the time does increase at the same rate for any N. My point was using an array introduces unnecessary logic that only works to make the end-result less efficient and slow - instead of reading numbers, think about reading classes with expensive constructors/destructors/copies and assignments.
stylin: Look up "big Oh" on time complexity of problems and algorthims. O(N) is linear complexity (for loop) and is always linear. Even if you do 1 for loop or 10 for loops (not nested for loops) its still going to be O(N) program/fuction. But if for some reason it took a nested for loop to do this program it would be O(N^2), but I don't see how anyone could make this program that complex. = ]
ToohrVyk: do you mean constant space? or constant time?
Quote:Original post by LostSource
stylin: Look up "big Oh" on time complexity of problems and algorthims. O(N) is linear complexity (for loop) and is always linear. Even if you do 1 for loop or 10 for loops (not nested for loops) its still going to be O(N) program/fuction.
Look, I think you're missing the point. I'm not talking about complexity. Yes, a for loop is a for loop is a for loop. But you don't seem to understand that adding more for loops will take longer for the program to complete.
Let me illustrate: If started at the same time, which of these two functions is going to finish before the other one?
namespace light { void waste_time() { for( int i=0; i<1000000; ++i ) ; }}namespace heavy { void waste_time() { for( int i=0; i<1000000; ++i ) ; for( int i=0; i<1000000; ++i ) ; for( int i=0; i<1000000; ++i ) ; for( int i=0; i<1000000; ++i ) ; for( int i=0; i<1000000; ++i ) ; for( int i=0; i<1000000; ++i ) ; for( int i=0; i<1000000; ++i ) ; for( int i=0; i<1000000; ++i ) ; for( int i=0; i<1000000; ++i ) ; for( int i=0; i<1000000; ++i ) ; }}
Author
thank you all for your help .
typing is not hte problem , but submitting the assignment at time is the difficult mission ,
I have worked on this homework fo about 5 hours only to produce this
typing is not hte problem , but submitting the assignment at time is the difficult mission ,
I have worked on this homework fo about 5 hours only to produce this
{ifstream infile;infile.open("number.txt");infile>>nb;infile>>x;//finding the maximum of the first half max=x; // assuming that the first number is the maximumfor ( int i=1 ; i < ((nb/2)) ; i++ ){ infile>>next; if ( next > max ) max=next; //changing the maximum if the next number is higher.}cout <<"The maximum of the first half is: "<<max<<endl;//finding the minimum of the second half. infile>>y;min=y;for ( int j=((nb/2)+1) ; j < nb ; j++ ){ infile>>next2; if ( next2 < min ) min=next2;}cout<<"The minimum of the second half is: "<<min<<endl;infile.close();}{ifstream infile;infile.open("number.txt");//finding the sum of all even numbersinfile>>nb;infile>>number; if ( number%2==0) sum=number; else sum=0;for ( int k=2 ; k<=nb ; k++ ){ infile>>num; if ( num%2==0 ) sum=sum+num; }cout<<"The sum of all even numbers is: "<<sum<<endl;infile.close();}//finding the average of all odd numbers{ifstream infile;infile.open("number.txt");infile>>nb;infile>>number2;counter=0;//to calculate the number of odd numbers that will be devided by thier sum. if ( number2%2!=0){ sum2=number2; counter=1;} else sum2=0;for ( int f=2 ; f<=nb ; f++ ){ infile>>num2;if ( num2%2!=0 ){sum2=sum2+num2;counter++;}} average=sum2/counter;cout<<fixed<<showpoint<<setprecision(2);cout<<"The average of all odd numbers is: "<<average<<endl;infile.close();} return 0;}Quote:Original post by LostSource
ToohrVyk: do you mean constant space? or constant time?
Quote:Original post by yours truly
Can you compute the maximum element of the second half of the list in constant space?
Quote:Original post by ToohrVyk
An interesting variation on this theme is:
You are given a list of integers, under the form of a function which returns the next integer when called, and a function which returns true if and only if there is a next integer. Can you compute the maximum element of the second half of the list in constant space?
I'm going to assume that it's possible, since you asked, but I have no idea how, short of storing every number in an array as you read them. Since that's linear space, I'm stumped. What's the solution?
Quote:Original post by stylinQuote:Original post by ToohrVyk
An interesting variation on this theme is:
You are given a list of integers, under the form of a function which returns the next integer when called, and a function which returns true if and only if there is a next integer. Can you compute the maximum element of the second half of the list in constant space?
I'm going to assume that it's possible, since you asked, but I have no idea how, short of storing every number in an array as you read them. Since that's linear space, I'm stumped. What's the solution?
It's impossible. But proving that you can't is hard (and along the lines of the proof that comparison-based sorts cannot perform faster than n log n).
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement