 Algorithm Analysis, Correctness and Sorted Linked List Algorithm

Subject Computer Science Data Structures and Algorithms

Question

The following algorithm checks if the array A is sorted in the ascending order.
isSorted(A)
n <- A.length
i <- 2
while i <= n
if A[i - 1] >A[i]
return false
i <- i + 1
return true
a) Give its best-case and worst-case running time. Justify your answer.
b) Using a suitable loop invariant, prove the correctness of the algorithm.
c) Write an algorithm to check if a linked list is sorted in the ascending order.

Solution Preview

This material may consist of step-by-step explanations on how to solve a problem or examples of proper writing, including the use of citations, references, bibliographies, and formatting. This material is made available for the sole purpose of studying and learning - misuse is strictly forbidden.

a) First of all, we notice that the algorithm can output “true” (sorted in ascending order) if and only if it is traversed the entire array. On the other hand, it can output “false” at any iteration of the “while” loop.
So the best case is achieved when the algorithm outputs “false” after a comparison (e.g. if a>a) or after a constant number of comparisons (by constant we consider a number c much less than input size n); in this case the algorithm requires O(1) (constant) effort...

This is only a preview of the solution. Please use the purchase button to see the entire solution

Related Homework Solutions

Benchmarking Bellman-Ford's Algorithm \$38.00
Bellman Ford
Algorithm
Graph
Single Source
Shortest Path
Critical Operation
Big-O
Analysis
Documentation
Test Plan
Complexity
Benchmark
Approach
Improvement
Dijkstra
Relaxation
Edge
Node
Lessons Learned
Minimum Spanning Tree Update Question in a Connected Graph \$5.00
MST
Minimum
Spanning
Tree
Connected
Undirected
Graph
Weight
Edge
O(V+E)
Algorithm
Increased
Modification
The Longest Increasing Subsequence Problem \$40.00
Programming
Computer Science
Longest Increasing Subsequence
Variables
Running Time
Algorithms
Complexity
Loops
Arrays
Two Dynamic Programming Algorithms: Rod Cutting & Minimum Number of Coins Change \$18.00
Dynamic
Programming
Algorithm
Complexity
Recurrence
Rod
Cut
Coin
Change
Amount
Integer
Denomination
Pseudocode
Maximum
DP
Sale
Unit
Piece
Price
Table
Bottom-up
Example
Analysis
Base
Case
Computer Engineering Questions \$4.00
Computer Science
Engineering
Intel 8086
Systems
DRAM Memory
RAS