Answered: Bubble sort pseudocode: Bubblesort (A,…

Database System Concepts

7th Edition

ISBN:9780078022159

Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Publisher:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Chapter1: Introduction

Section: Chapter Questions

Problem 1PE

See similar textbooks

Related questions

Question

Bubble sort pseudocode: Bubblesort (A, n)

// A is array, n items to sort

For i = n-1 to 1

For j = 1 to i If A[j] < A[j+1]

Swap (A[j], A[j+1])

(A) Determine the big-O running time (tight bound) of bubble sort in the left column. Show your derivation. This pseudocode assumes the array starts at index 1. Count comparisons as the critical operation. Your solution should count the exact number of comparisons as a function of n (number of items being sorted). In converting your formula for number of comparisons to a closed-form formula (as opposed to a summation formula), you do not need to show the derivation (such as writing the summation twice and dividing by two), though it is okay to do that. You do need to show the closed-form formula for exact number of comparisons, before simplifying it to a big-O representation.

As a reference, study the stairs examples in the book. See figure 1.2, pg. 20.

(B) Prove that f(n) = 1000n5 + 20000n2 + 32 is O(n6 ); Is this a tight upper bound? Why or why not?

20 Chapter 1 / The Phases of Software Development
The value of twice the expression is n multiplied by n+ 1. We are now essen-
tially done. The number we computed is twice the quantity we want. So, to
obtain our simplified formula, we only need to divide by 2. The final simplifica-
tion is thus:
n(n + 1)
(1+2 + ... +n)
2
We will use this simplified formula to rewrite the Technique 2 time expres-
sion, but you'll also find that the formula occurs in many other situations. The
simplification for the Technique 2 expression is as follows:
Number of operations for Technique 2
=n+ 2(1 +2 +... +n)
= n+ 2 (n(n+ 1)) Plug in the formula for (1+2 +... +n)
— п+ n(n + 1)
Cancel the 2s
— п+ n +n
Multiply out
= n? + 2n
Combine terms
So, Technique 2 requires n? + 2n operations.
FIGURE 1.2 Deriving a Handy Formula
(1+2 +... +n) can be computed by first computing the sum of twice (1+2 +... +n), as
shown here:
1
+
+ ... + (n – 1) +
n
+ (n – 1) + ... +
(п +1) + (п+1) +
+
n
2
1
+ (п+1) + (п +1)
...
The sum is n(n + 1), so (1 +2 +... +n) is half this amount:
n(n+ 1)
(1 +2 +... +n)
2

Expert Solution

Trending now

This is a popular solution!

Step by step

Solved in 2 steps

SEE SOLUTION Check out a sample Q&A here

Knowledge Booster

Learn more about

Need a deep-dive on the concept behind this application? Look no further. Learn more about this topic, computer-science and related others by exploring similar questions and additional content below.

Similar questions