Algorithms

Question 1

space complexity for the sorting algorithms

Answer 1

IDK

Question 2

for(int i =0 ; I < n; I++)
for(j =0 ; j < I ; j++)
how man times does the second loop perform?
what is the complexity of these two?

Answer 2

1. n * (n - 1) / 2
2. O(n**2)

Question 3

if you have a difficult loops to analyze, what should you do?

Answer 3

you should trace the variables (I,j)..

Question 4

what is the complexity time for
for( I = 0 ; I < n, I++)

Answer 4

O(n)

Question 5

what is the complexity time for
for( I = 0 ; I < n, I= I+2)

Answer 5

n/2 = O(N)

Question 6

what is the complexity time for
for( I = 0 ; I < n, I–)

Answer 6

o(n)

Question 7

what is the complexity time for
for( I = 0 ; I < n, I= I*2)

Answer 7

O(logn)

Question 8

how we determined what sorting algorithm to use?

Answer 8

1. Time Complexity
2. Space Complexity
3. Internal Sort or External Sort:
   Internal: load the data into memory
   External Sort: data on disk
4. Recursive or Non recursive

Question 9

explain Selection sort shortly

Answer 9

select the minimum and and move it to the sorted part at the beginning.

Question 10

what is the psudu code for selection sort

Answer 10

for I in range(n -1):
iMin = I
for j in range(I+1, n):
if A[j] < A[iMin]:
iMin=j
temp = A[I]
A[I] = A[iMin]
A[iMin] = temp

com = O(N**2)

Question 11

can you explain Bubble Sort shortly?

Answer 11

we move the large elements to the right by swapping the left element (large) with right element(small).

Question 12

what is the pseudo code for Bubble sort?
how can you improve the regular Bubble sort?

Answer 12

for k in range(1, n - 1):
for I in range (0, n -k -1): # -k because the right elements are sorted.
If A[I] > A[I + 1]:
swap(A[I], A[I+1])

Com = O(N**2)
we can improve it by adding flag on the big loop, when we have swap we change it to true, and before we finish the big loop, we check if it’s false. so we can return