Results 1 to 9 of 9
  1. #1
    romavolman is offline Member
    Join Date
    Sep 2012
    Posts
    4
    Rep Power
    0

    Default Time complexity question

    I have method and I need to improve the time complexity.
    Method accept two array with same size with hole positive numbers and
    Third empty array.How i can improve complexity time in this method ?
    public int f(int[] a, int[] b, int[] c)
    {
    int N = a.length();
    int k=0, t=0, p=0;
    for(int i = 0; i<N; i++)
    {
    for(int j = 0; j<N; j++)
    {
    if(a[i] == b[j])
    brake;
    }

    c[t]=a[i];
    if(p==0 || c[t]>k)
    {
    k = c[t];
    p = 1;

    }
    t++;
    }

    return k;
    }

  2. #2
    DarrylBurke's Avatar
    DarrylBurke is offline Forum Police
    Join Date
    Sep 2008
    Location
    Madgaon, Goa, India
    Posts
    11,457
    Rep Power
    20

    Default Re: Time complexity question

    BB Code List - Java Programming Forum

    Are yoiu sure that's Java code?
    Quote Originally Posted by romavolman View Post
    brake;
    db
    If you're forever cleaning cobwebs, it's time to get rid of the spiders.

  3. #3
    romavolman is offline Member
    Join Date
    Sep 2012
    Posts
    4
    Rep Power
    0

    Default Re: Time complexity question

    I have method and I need to improve the time complexity.
    Method accept two array with same size with hole positive numbers and
    Third empty array.How i can improve complexity time in this method ?
    public int f(int[] a, int[] b, int[] c)
    {
    int N = a.length();
    int k=0, t=0, p=0;
    for(int i = 0; i<N; i++)
    {
    for(int j = 0; j<N; j++)
    {
    if(a[i] == b[j])
    break;
    }


    if(j==N)
    {


    c[t]=a[i];
    if(p==0 || c[t]>k)
    {
    k = c[t];
    p = 1;

    }
    t++;
    }

    }

    return k;
    }

  4. #4
    kjkrum's Avatar
    kjkrum is offline Senior Member
    Join Date
    Apr 2011
    Location
    Tucson, AZ
    Posts
    1,060
    Rep Power
    6

    Default Re: Time complexity question

    It's very hard to understand when you use meaningless letters for variable names.
    Get in the habit of using standard Java naming conventions!

  5. #5
    DarrylBurke's Avatar
    DarrylBurke is offline Forum Police
    Join Date
    Sep 2008
    Location
    Madgaon, Goa, India
    Posts
    11,457
    Rep Power
    20

    Default Re: Time complexity question

    Also hard to help you when you don't bother to click a link in a response to find why it was offered.

    db
    If you're forever cleaning cobwebs, it's time to get rid of the spiders.

  6. #6
    romavolman is offline Member
    Join Date
    Sep 2012
    Posts
    4
    Rep Power
    0

    Default Re: Time complexity question

    what method f do: method "f" fill emptyArr with numbers of arr1 that the method "f" don't find in arr2 and return the biggest number in arr1 that the method "f" canot
    find in arr2.
    given information - arr1.length == arr2.length, arr1 and arr2 full with whole positive numbers.

    qustion is : how to improve the time complexity of this method ???


    public int f(int[]arr1, int[]arr2, int[] emptyArr)
    {
    int length = a.length;
    int k = 0, g = 0, index = 0;

    for(int i=0; i < length; i++)
    {
    for(int j=0; j < length; j++)
    if(arr2[j] == arr1[i])
    break;

    if(j == length)
    {
    emptyArr[index] = arr1[i];
    if(g == 0 || emptyArr[index] > k) // find the max of arr1 that you don't have in arr2
    {
    k = emptyArr[index]; // max of arr1 that you don't have in arr2
    g = 1;

    }
    index++;

    }


    }
    return k; // max of arr1 that you don't have in arr2 .
    }

    }
    Last edited by romavolman; 09-18-2012 at 04:28 PM.

  7. #7
    DarrylBurke's Avatar
    DarrylBurke is offline Forum Police
    Join Date
    Sep 2008
    Location
    Madgaon, Goa, India
    Posts
    11,457
    Rep Power
    20

    Default Re: Time complexity question

    If you continue to ignore the link provided in the first response, this thread will be locked and you may be banned for a period.

    Using code tags is not optional.

    db
    If you're forever cleaning cobwebs, it's time to get rid of the spiders.

  8. #8
    Norm's Avatar
    Norm is offline Moderator
    Join Date
    Jun 2008
    Location
    Eastern Florida
    Posts
    17,903
    Rep Power
    25

    Default Re: Time complexity question

    Also posted at time complexity qustion
    If you don't understand my response, don't ignore it, ask a question.

  9. #9
    sterf is offline Member
    Join Date
    Apr 2012
    Posts
    6
    Rep Power
    0

    Default Re: Time complexity question

    Romavolman i agree with other posts that your text is vague.

    Perhaps you mean by "time complexity" simply how to make the code run faster, and that implies that you had array sizes in the millions. i guess that your goal is to fill c[] with some local maxima. If that is the case, what you want is to remove the input array cell that you have used, and you did not do that because of the limitations of the datatype array. Correct?

    The problem is that you use NxN combinations, that is brute force and will take forever.

    Suggestion: first order the a[] and then order the b[]. Then loop once, keeping two pointers p_a and p_b, and then you have only N comparisons. Ordering a list of n elements like a[] and b[] you can use standard method like quicksort, that takes N*log(N) time. So from
    NxN you improve your "time complexity" to 3N*log(N).

    Good luck!

Similar Threads

  1. time complexity of toArray
    By marcosol in forum New To Java
    Replies: 13
    Last Post: 09-19-2012, 07:51 PM
  2. I need help with Time Complexity???
    By lulzim in forum Advanced Java
    Replies: 2
    Last Post: 09-20-2011, 10:11 AM
  3. I need help for Time Complexity of this???
    By lulzim in forum Advanced Java
    Replies: 9
    Last Post: 09-16-2011, 04:51 PM
  4. time complexity questions
    By myst in forum New To Java
    Replies: 6
    Last Post: 07-13-2010, 12:02 PM
  5. Replies: 2
    Last Post: 11-04-2008, 03:48 AM

Tags for this Thread

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •