Andreas Martinus was the son of Ole Andersen. "Olsen" means "son of Ole". Traditionally, he wold have received the name "Andreas Martinus Olsen" at birth.
Often, when Norwegian emigrated, they took their fatjer's last name instead. This was often the case when families emigratd together as they were expected to all have the same last name in America. Therefore, he could easily have used "Andreas Martinus Andersen" later in life.
In those times, names were not changed legally. The People just made the choice and used it.
As I posted above, his mother was Magdeli Monsdatter. They were from the parish "Sæbo", which was a sub-parish of "Manger" in Hordaland.