Welcome to the Java Programming Forums


The professional, friendly Java community. 21,500 members and growing!


The Java Programming Forums are a community of Java programmers from all around the World. Our members have a wide range of skills and they all have one thing in common: A passion to learn and code Java. We invite beginner Java programmers right through to Java professionals to post here and share your knowledge. Become a part of the community, help others, expand your knowledge of Java and enjoy talking with like minded people. Registration is quick and best of all free. We look forward to meeting you.


>> REGISTER NOW TO START POSTING


Members have full access to the forums. Advertisements are removed for registered users.

Results 1 to 3 of 3

Thread: Can I get help with a few Data Structures questions?

  1. #1
    Junior Member
    Join Date
    Apr 2013
    Posts
    23
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Can I get help with a few Data Structures questions?

    I currently taking a class on data structures and we had recitation and there are a few questions I don't quite understand how to solve.

    Please explain how to do these questions

    1.)
    (a) [7.5 minutes] Write psuedocode for an O(n)-time algorithm for finding that number. Use an additional array of size n+1 to help you. Verify that the algorithm is O(n).

    (b) [7.5 minutes] Write pseudocode for an O(n)-time algorithm for finding that number, but use only a constant amount of additional space besides the array A itself. Verify that the algorithm is O(n) and the extra space used is O(1).



    2.) What is the number of operations (assignment statements) that occur in the following code fragment in closed form in terms of n? In Big O notation? (Note: Ignore assignment operators inside loop headers and you may assume n is a power of 2)

    int d = 0;
    for(int i = 1; i <= n; i++)
    { for(int j = 1; j <= i; j++)
    d = d + i + j;
    d = d + 2;
    }
    for(int k = 1; k < n; k = k*2)
    { d = d – 5;
    }

    I thought that the answer was n^2 + log base 2 * n

    b/c the first two loops run n times and have I assignment in each and the last loop multiplies k by 2.

    But the actual answer is Closed: ((n2 + n)/2 + n) + (log2 n)) + 1
    Big O: O(n2) "

    3.)((log2 n)3 + n/8 - I thought the order of complexity was O(logn) but it's actually O(n).
    Can someone please explain these answers thoroughly?


  2. #2
    Junior Member
    Join Date
    Apr 2013
    Posts
    23
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Can I get help with these data structures questions?

    I currently taking a class on data structures and we had recitation and there are a few questions I don't quite understand how to solve.

    Please explain how to do these questions

    1.)
    (a) [7.5 minutes] Write psuedocode for an O(n)-time algorithm for finding that number. Use an additional array of size n+1 to help you. Verify that the algorithm is O(n).

    (b) [7.5 minutes] Write pseudocode for an O(n)-time algorithm for finding that number, but use only a constant amount of additional space besides the array A itself. Verify that the algorithm is O(n) and the extra space used is O(1).



    2.) What is the number of operations (assignment statements) that occur in the following code fragment in closed form in terms of n? In Big O notation? (Note: Ignore assignment operators inside loop headers and you may assume n is a power of 2)

    int d = 0;
    for(int i = 1; i <= n; i++)
    { for(int j = 1; j <= i; j++)
    d = d + i + j;
    d = d + 2;
    }
    for(int k = 1; k < n; k = k*2)
    { d = d 5;
    }

    I thought that the answer was n^2 + log base 2 * n

    b/c the first two loops run n times and have I assignment in each and the last loop multiplies k by 2.

    But the actual answer is Closed: ((n2 + n)/2 + n) + (log2 n)) + 1
    Big O: O(n2) "

    3.)((log2 n)3 + n/8 - I thought the order of complexity was O(logn) but it's actually O(n).
    Can someone please explain these answers thoroughly?

  3. #3
    Super Moderator jps's Avatar
    Join Date
    Jul 2012
    Posts
    2,642
    My Mood
    Daring
    Thanks
    90
    Thanked 263 Times in 232 Posts

    Default Re: Can I get help with a few Data Structures questions?

    Please do not duplicate post
    Threads merged

Similar Threads

  1. Help: Data Structures and Data Types
    By TheLawG14 in forum Java Code Snippets and Tutorials
    Replies: 2
    Last Post: July 19th, 2013, 10:55 AM
  2. data structures question
    By hwoarang69 in forum Algorithms & Recursion
    Replies: 2
    Last Post: November 4th, 2012, 03:07 PM
  3. Please help about data structures.
    By bruce88 in forum What's Wrong With My Code?
    Replies: 4
    Last Post: September 16th, 2012, 05:11 PM
  4. [SOLVED] O(log n): a simple question for Logarithm in Data structures & Algo
    By chronoz13 in forum Algorithms & Recursion
    Replies: 1
    Last Post: September 7th, 2012, 09:20 AM
  5. [SOLVED] Data Structures: Symbolic Algebra with Trees
    By Staticity in forum What's Wrong With My Code?
    Replies: 2
    Last Post: August 20th, 2012, 02:42 AM