Foundations for Algorithmic Thinking: Estimating the Growth of Functions

• In Event: AERA Poster Session 13
  In Poster Session: Technology, Instruction, Cognition and Learning SIG Poster Session (San Diego)

Abstract

STEM education increasingly prioritizes computational thinking, including algorithmic thinking––mathematical analysis of algorithms and data structures. Analyzing an algorithm includes identifying the function that specifies its computational complexity for an input. The current study investigated undergraduates’ estimation of the growth of functions with increasing input size. They estimated values of seven functions that commonly arise in algorithmic analysis [, , , , , , ] for . Estimates were fit against the actual values for all seven functions. Participants’ estimates were generally accurate. Sublinear estimates were best fit by sublinear functions, and superlinear estimates by superlinear functions. Participants estimated logarithmic functions least accurately. These results inform future instructional studies on improving intuitions about the growth of functions and algorithmic thinking.

Authors

• Vijay Marupudi, Georgia Institute of Technology

• Jeffrey K. Bye, University of Minnesota - Twin Cities

• Sashank Varma, Georgia Tech