Assignment 1
RESULTS
The time complexity of binary search method is a factor of a. Binary search is an effective
approach for locating a target value in a sorted array. Until the goal value is found or the
interval is empty, it operates by halving the search interval periodically.
The algorithm operates as follows:
Start with the whole array.
Return the middle element's index if target value is the same as the array's middle element.
The search should be repeated on the sub-array to the left of the middle element if the target
value is smaller than the middle element.
Proceed with the search on the sub-array located to the right of the center element if the target
value exceeds it.
Continue doing this until either the sub-array is empty or the target value is located.
The binary search algorithm has an O(log n) time complexity, where n is the array's element
count. This is due to the fact that the search space shrinks by half with each round.
b.
sorted array [2, 5, 8, 12, 16, 23, 38, 56, 72, 91, 102, 128, 192, 256] to find the target value 91:
Initialization:
low = 0, high = 13 (indices of the first and last elements in the array).
mid = = 6 (middle index).
Iteration 1:
Compare the target value 91 with the middle element array[mid] = 38.
Since 91 is greater than 38, update low = mid = 7 (new low index).
Iteration 2:
Calculate new mid = 10.
Compare 91 with array[mid] = 102.
Since 91 is less than 102, update high = mid - 1 = 10 - 1 = 9 (new high index).
Iteration 3:
Calculate new mid = 8.
Compare 91 with array[mid] = 72.
Since 91 is greater than 72, update low = mid + 1 = 8 + 1 = 9 (new low index).
Iteration 4:
Calculate new mid = 9.
Compare 91 with array[mid] = 91.
Match found, return mid = 9.
Result:
The target value 91 is found at index 9 in the array.
c. Comparison between Linear Search and Binary Search:
Linear search: This method goes through each element of the array one after the other until the
target value is discovered or the array's end is reached. O(n), where n is the number of items in
the array, is the time complexity. Unsorted arrays are a good fit for linear search.
Binary Search: Sorting the array is necessary. For big arrays, it is significantly quicker than linear
search as it repeatedly divides the search interval in half. O(log n), where n is the array's
element count, is the time complexity.
d. Scenario where Linear Search might be Preferred over Binary Search:
Small Arrays: Sorting an array for binary search may be more work than it is worth for very
small arrays. Linear search is more effective in these situations.
Unsorted Arrays: The sole alternative in cases when sorting an array is not feasible is to use
linear search.
Requirement for Simplicity: Compared to binary search, linear search is easier to use and
comprehend. Linear search may be selected if the algorithm's simplicity is more essential than
its efficiency.
2.
Job 1: Required time = 25, Deadline = 50
Job 2: Required time = 15, Deadline = 60
Job 3: Required time = 20, Deadline = 60
Job 4: Required time = 5, Deadline = 55
Job 5: Required time = 10, Deadline = 75
Let's calculate the lateness of each job:
Job 1: Lateness = max(0, 25 - 50) = 0
Job 2: Lateness = max(0, 40 - 60) = 0
Job 3: Lateness = max(0, 60 - 60) = 0
Job 4: Lateness = max(0, 65 - 55) = 10
Job 5 Lateness = max(0, 75 - 75) = 0
The maximum lateness is 10, which occurs when Job 4 is completed.
Job [1], Job [2], Job [3], Job [4], Job [5].
3.
It is 40. For example with greedy algorithm we will choose 25 then 12 then 1 then 1 then 1.That is 5
coins.And optimal way is 4*10 which is 40 and we used 4 coins. 4>5
4.
function exampleAlgorithm(arr):
n = length(arr)
count = 0
for i from 0 to n:
for j from i+1 to n:
for k from j+1 to n:
count = count + log(n)
return count
arr = [1, 2, 3, ..., n]
result = exampleAlgorithm(arr)
This is logarithmic complexity and for that time complexity is O(nlogn) since we have three for loops
here the time complexity of n^3logn will be O(n^3logn)
O(n^3logn)= n^3*logn^3
=n^3*3logn
= 3*n^3logn
=C1*n^3logn
It is n^3logn.
5.
Initial list: {f, k, l, j, o, u, t, g, h, n}
Split the list into halves:
Left sublist: {f, k, l, j, o}
Right sublist: {u, t, g, h, n}
Sort the left sublist:
Split {f, k, l, j, o} into halves:
Left sublist: {f, k}
Right sublist: {l, j, o}
Sort each half:
Left sublist: {f, k} (No change, already sorted)
Right sublist: {j, l, o} (Sort to {j, l, o})
Merge the sorted halves: {f, j, k, l, o}
Sort the right sublist:
Split {u, t, g, h, n} into halves:
Left sublist: {u, t, g}
Right sublist: {h, n}
Sort each half:
Left sublist: {g, t, u} (Sort to {g, t, u})
Right sublist: {h, n} (No change, already sorted)
Merge the sorted halves: {g, h, n, t, u}
Merge the two sorted sublists:
Left sublist: {f, j, k, l, o}
Right sublist: {g, h, n, t, u}
Merge into a single sorted list: {f, g, h, j, k, l, n, o, t, u}
Final sorted list: {f, g, h, j, k, l, n, o, t, u}
6.
recursive min(n: positive integer, a1, a2, a3, ..., an : integers)
if n = 1 then
return a1
else
return min(an, recursive min(n - 1, a1, 02, 03, .., an-1))
end if
{output is the minimum integer}
7.
a) an = [10]n + 5
Recursive definition an=an−1+10
n = 1: a1 = 10*1 + 5 = 10 + 5 = 15
n = 2: a2 = 10*2 + 5 = 20 + 5 = 25
n = 3: a3 = 10*3 + 5 = 30 + 5 = 35
b) an = [35] + (-1)^n
Recursive definition an=an−1+(−1)n
n = 1: a1 = [35] + (-1)^1 = 35 + (-1) = 34
n = 2: a2 = [35] + (-1)^2 = 35 + 1 = 36
n = 3: a3 = [35] + (-1)^3 = 35 + (-1) = 34
c) an = n(n + [15])
n = 1: a1 = 1(1 + [15]) = 1(1 + 15) = 1(6) = 6
n = 2: a2 = 2(2 + [15]) = 2(2 + 15) = 2(17) = 34
n = 3: a3 = 3(3 + [15]) = 3(3 + 15) = 3(18) = 54
d) an = [5]*n^[6]
n = 1: a1 = [5]*1^[6] = 5 * 1 = 5
n = 2: a2 = [5]*2^[6] = 5*64=320
n = 3: a3 = [5]*3^[6] = 5 * 729 = 3645
