Thread: 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?

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?

Please do not duplicate post
Threads merged