10 Replies - 421 Views - Last Post: 29 January 2013 - 11:06 AM Rate Topic: -----

#1 Maria23  Icon User is offline

  • D.I.C Head

Reputation: 2
  • View blog
  • Posts: 77
  • Joined: 24-November 12

complexity question

Posted 28 January 2013 - 11:02 AM

what is the complexity of my code? is it nlogn or more?>
dnt worry its not a homework i have exam im solving questions, this comlexity things complicate me !!
this is my code:
(the question wanted to print the most numbers possiple from the array in condition the sum of these numbers is not higher than max, with O(nlogn) complexity)

for example: 6,1,-8,-12,37,38,39,15 and max=0 the output is 6,1,-8,-12.

void print_max(int a[], int n, int max) /* n is the length of the array, max is any number */
{
    int sum=0, i=0;
    merge_sort(a,n); \* merge_sort comlexity is nlogn */
    while(sum<=max)
    {
        sum+=a[i];
        i++;
        printf("%d, ",a[i]);
    }
    
}



Is This A Good Question/Topic? 0
  • +

Replies To: complexity question

#2 vividexstance  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 630
  • View blog
  • Posts: 2,107
  • Joined: 31-December 10

Re: complexity question

Posted 28 January 2013 - 11:12 AM

If max is equal to the sum of all the numbers in the array, then what would the while-loops complexity be?
Was This Post Helpful? 0
  • +
  • -

#3 Maria23  Icon User is offline

  • D.I.C Head

Reputation: 2
  • View blog
  • Posts: 77
  • Joined: 24-November 12

Re: complexity question

Posted 28 January 2013 - 11:30 AM

O(n) :'(
so that means my solution is wrong :( i cant solve it in nlogn
im bad with complexity
Was This Post Helpful? 0
  • +
  • -

#4 Maria23  Icon User is offline

  • D.I.C Head

Reputation: 2
  • View blog
  • Posts: 77
  • Joined: 24-November 12

Re: complexity question

Posted 28 January 2013 - 12:09 PM

cant u give me a hint please how to solve it with nlogn ??!!
Was This Post Helpful? 0
  • +
  • -

#5 vividexstance  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 630
  • View blog
  • Posts: 2,107
  • Joined: 31-December 10

Re: complexity question

Posted 28 January 2013 - 01:30 PM

This link may help you: http://en.wikipedia..../Master_theorem or this link: http://stackoverflow...algorithm-big-o.

I'm not just going to give you the answer, but with those 2 links and the power of google, you should be able to figure it out. If not, post again and explain the problem you're having or what you don't understand.
Was This Post Helpful? 0
  • +
  • -

#6 Maria23  Icon User is offline

  • D.I.C Head

Reputation: 2
  • View blog
  • Posts: 77
  • Joined: 24-November 12

Re: complexity question

Posted 28 January 2013 - 11:55 PM

tell me is this works?
/* binsearch takes logn time, i dont need search in my code!, but if the search takes O(logn) time and i searched n times each search costs O(logn), so all n searches cost O(nlogn) */
so????? is it all nlogn??
void print_max(int a[], int n, int max)
{
    int sum=0, i=0;
    merge_sort(a,n);
    while(sum<=max)
    {
        binsearch(a[i],a,0,n);  
        sum+=a[i];
        i++;
        printf("%d ",a[i]);
    }
    
}

This post has been edited by jimblumberg: 29 January 2013 - 05:49 AM
Reason for edit:: Added missing code tags. Please learn to use them properly.

Was This Post Helpful? 0
  • +
  • -

#7 mojo666  Icon User is offline

  • D.I.C Addict
  • member icon

Reputation: 337
  • View blog
  • Posts: 728
  • Joined: 27-June 09

Re: complexity question

Posted 29 January 2013 - 08:07 AM

The math is correct but you kind of miss the point of big O. If you are given a requirement for how fast your algorithm needs to run, and you come up with a solution that is faster, then you have met the requirement. O(n)<O(nlogn) so you have met the requirement. You don't need to make it slower.

However, I also think your understanding of the complexity of the algorithm is off.

void print_max(int a[], int n, int max) /* n is the length of the array, max is any number */ 
{  
     int sum=0, i=0;  
     merge_sort(a,n); \* merge_sort comlexity is nlogn */  
     while(sum<=max)  
     {  
         sum+=a[i];  
         i++;  
         printf("%d, ",a[i]);  
     }  
}



The mergesort is O(nlogn) and the while loop is O(n). What is the complexity of the whole algorithm?

This post has been edited by mojo666: 29 January 2013 - 08:08 AM

Was This Post Helpful? 0
  • +
  • -

#8 Maria23  Icon User is offline

  • D.I.C Head

Reputation: 2
  • View blog
  • Posts: 77
  • Joined: 24-November 12

Re: complexity question

Posted 29 January 2013 - 10:10 AM

i dont know !!.. if i knew i wouldnt ask for help ! thats the thing i dnt know what O(nlogn)+O(n) equals !! i missed the lescture and i didnt understand the material very well alone!
so what does it equal??
(dont post a link for me i didnt understand the links been posted for me i dnt understand english ver well) please help i have alot of questions to solve
Was This Post Helpful? 0
  • +
  • -

#9 vividexstance  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 630
  • View blog
  • Posts: 2,107
  • Joined: 31-December 10

Re: complexity question

Posted 29 January 2013 - 10:39 AM

When you go to school and have questions like this, your professor/teacher is there for you to ask questions like this.

With Big-O notation, you don't add them together, whatever the highest complexity is, thats the complexity for the whole function. So because the while loop is O(n) and the sort is O(nlogn), the complexity is the higher of the two.
Was This Post Helpful? 0
  • +
  • -

#10 mojo666  Icon User is offline

  • D.I.C Addict
  • member icon

Reputation: 337
  • View blog
  • Posts: 728
  • Joined: 27-June 09

Re: complexity question

Posted 29 January 2013 - 10:43 AM

Alright, so you know that it is O(nlogn)+O(n)....which is the same as O(nlogn+n).

I'm not sure how much you've missed, but in complexity we drop constant multiples and constant additions. So something like O(5n+3) is the same as O(n). This also allows us to drop lower terms. So something like O(n^2 + n) is the same as O(n^2). The reason we can do this is because if n < n^2 then n^2 < n^2+n < n^2+n^2. If we apply big O to all the terms we get O(n^2)<O(n^2+n)<O(2n^2). Since we can drop constant multiples we actually have O(n^2)<O(n^2+n)<O(n^2), so O(n^2+n) must be the same complexity as O(n^2)

So, in O(nlogn + n) you have two terms, and you can drop the lowest.
Was This Post Helpful? 1
  • +
  • -

#11 Maria23  Icon User is offline

  • D.I.C Head

Reputation: 2
  • View blog
  • Posts: 77
  • Joined: 24-November 12

Re: complexity question

Posted 29 January 2013 - 11:06 AM

yes i know that rules but i didnt know i can use it here (cuz of the nlogn, its lil bit scary lol) ... thnx alot

ok next time i will ask:)
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1