This is a read-only archive of the old Scratch 1.x Forums.
Try searching the current Scratch discussion forums.

#1 2012-06-19 12:08:11

MyraUK
New Scratcher
Registered: 2012-06-16
Posts: 6

runtime of list operations?

I've been playing around with list operations in Scratch. I had the idea that kids in the last couple of years of primary (elementary) school could do some cross-curricular activities by implementing statistics like mean, median, and mode in Scratch. Since I'm only going to be dealing with numbers 1-100 in my data (I want to do stats on data collected from the Picoboard) what I need is a bucket sort. To do mode, I put all the data into buckets (one per number) and find which bucket has the largest number of items in it. To do median, I go through the buckets until I've found half of my data, then I'm at the median. Average is pretty straightforward.

What is the runtime of a random access of a list operation? If I do

replace item [25] of [buckets v] with <<item [25] of buckets> + 1>
(Sorry I couldn't get the Scratch blocks just right...)

Is the runtime (big-O) of this 1 or 25?

I need to know this, as we'll be working with some fairly long lists... It will influence how I implement my bucket sort.

Offline

 

#2 2012-06-19 12:34:04

blob8108
Scratcher
Registered: 2007-06-25
Posts: 1000+

Re: runtime of list operations?

Intuitively I'd say 1, not 25 — this post by bharvey seems to agree.  smile


Things I've made: kurt | scratchblocks2 | this cake

Offline

 

#3 2012-06-19 13:17:15

MyraUK
New Scratcher
Registered: 2012-06-16
Posts: 6

Re: runtime of list operations?

Yup, that's quite clear! Thank you, that is exactly what I needed to know.

Offline

 

Board footer