/sci/ - Science & Math » Thread #12476015

80KiB, 1506x312, file.png

View Same Google iqdb SauceNAO

What is the time and space complexity of this whole algorithm?

Anonymous Thu 17 Dec 14:33:20 2020 No.12476015 View Reply Original Report

Quoted By: >>12476287

Anonymous

Anonymous Thu 17 Dec 2020 15:50:55 No.12476287 Report

Quoted By: >>12476560

>>12476015
Time: O(n*log n + log n)
Space: O(n)

t. CS nigger

Anonymous

Anonymous Thu 17 Dec 2020 17:32:12 No.12476560 Report

Quoted By: >>12476634

>>12476287
why nlogn in time? where does this log(n) come from?

Anonymous

Anonymous Thu 17 Dec 2020 17:49:51 No.12476634 Report

Quoted By: >>12478550

>>12476560
Method1 will iterate through a fraction of the tree's nodes, and that fraction is best represented as log n. Since you're calling it n times from main, you get the nlogn.
Also, I may have made a mistake there. If method2 goes through all of the tree's nodes, then time complexity is nlogn + n.

Anonymous

Anonymous Fri 18 Dec 2020 02:59:34 No.12478550 Report

Quoted By: >>12479641

>>12476634
O(nlogn) in average case. it is possible that the input array items is strictly increasing or decreasing, in which case method1 takes O(n) time, making the tie complexity of main O(n^2)

Anonymous

Anonymous Fri 18 Dec 2020 10:54:51 No.12479641 Report

Quoted By:

>>12478550
you are right

Capcode	All Only User Posts Only Moderator Posts Only Admin Posts Only Developer Posts
Show Posts	All Only With Images Only Without Images
Deleted Posts	All Only Deleted Posts Only Non-Deleted Posts
Ghost Posts	All Only Ghost Posts Only Non-Ghost Posts
Post Type	All Only Sticky Threads Only Opening Posts Only Reply Posts
Results	All Grouped By Threads
Order	Latest Posts First Oldest Posts First

Your latest searches