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

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

1. ## 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).  Reply With Quote

3. ## 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).  Reply With Quote
4. ## Re: Can I get help with a few Data Structures questions?  Reply With Quote