As he emigrated to America, Norwegian name rules don't really apply. Besides, it's obvious that he called himself Berntsen from early on. Until 1923, Norwegians didn't have "official" surnames, and that's why you generally won't find one in the baptism records. Basically, they could call themselves whatever they wanted.
I see that he's born in Stavanger, a pretty large city by Norwegian standards, and many city dwellers by the 1830s had already abandoned patronymics for inheritable surnames. In particular, if the father was a burgher, ie. a merchant, sea captain, or certified craftsman, the family was expected to have an inheritable surname. So, the rule of patronymic for LNAB is not that hard-and-fast, even in the early 19th century.