Notes
Notes - notes.io |
The worst case scenario happens when the heap is built with an array of numbers in reverse order (from largest to smallest). A heap built in such a way would require the swapUp function to traverse from the position it is currently handling all the way to the top. Because heaps are balanced trees, the maximum amount of time that each swapUp can take is log(n), making nlog(n) an upper bound of the asymptotic time it takes to run swapUp on each heap element. Since the number of leaf nodes is always more than half of the total number of nodes, and since each leaf node requires log(n) time to traverse up to the top of the heap, the mean asymptotic time of running swapUp on each heap element can be lower bounded by nlog(n)/2, which asymptotically equals nlog(n). With upper and lower bounds of nlog(n), the asymptotic Big-theta worst running time of heapify2 is nlog(n)
b) Best case is n, you need to run swapDown for each element in the heap, but since there is nothing in need of swapping, swapDown takes constant time.
c) Best case is n, you need to run swapUp for each element in the heap, but since there is nothing in need of swapping, swapUp takes constant time.
d) I am running this program on a Macbook. It took 4 seconds to finish running when REPS was set to 400,000
e)
100 - 4 seconds
200 - 8 seconds
300 - 12 seconds
400 - 17
500 - 22
600 - 26
700 - 30
800 - 34
900 - 39
1000 - 43
f)
100 - 2
200 - 4
300 - 5
400 - 7
500 - 9
600 - 11
700 - 12
800 - 14
900 - 15
1000 - 17
g)
100 - 1
200 - 2
300 - 4
400 - 6
500 - 7
600 - 9
700 - 10
800 - 11
900 - 13
1000 - 14
h)
100 - 10
200 - 23
300 - 38
400 - 54
500 - 79
600 - 9
700 - 10
2.
Notes:
Base Case: (prove the invariant true before the first loop guard test)
Just before
Inductive Case
Termination
(portion of the array that is covered by intervals on the stack)
|
|
Notes.io is a web-based application for taking notes. You can take your notes and share with others people. If you like taking long notes, notes.io is designed for you. To date, over 8,000,000,000 notes created and continuing...
With notes.io;
- * You can take a note from anywhere and any device with internet connection.
- * You can share the notes in social platforms (YouTube, Facebook, Twitter, instagram etc.).
- * You can quickly share your contents without website, blog and e-mail.
- * You don't need to create any Account to share a note. As you wish you can use quick, easy and best shortened notes with sms, websites, e-mail, or messaging services (WhatsApp, iMessage, Telegram, Signal).
- * Notes.io has fabulous infrastructure design for a short link and allows you to share the note as an easy and understandable link.
Fast: Notes.io is built for speed and performance. You can take a notes quickly and browse your archive.
Easy: Notes.io doesn’t require installation. Just write and share note!
Short: Notes.io’s url just 8 character. You’ll get shorten link of your note when you want to share. (Ex: notes.io/q )
Free: Notes.io works for 12 years and has been free since the day it was started.
You immediately create your first note and start sharing with the ones you wish. If you want to contact us, you can use the following communication channels;
Email: [email protected]
Twitter: http://twitter.com/notesio
Instagram: http://instagram.com/notes.io
Facebook: http://facebook.com/notesio
Regards;
Notes.io Team
