How is not halting O(1)? Wouldn't that be O(∞)? | Hacker News

Hacker Newsnew | past | comments | ask | show | jobs | submit

		tempodox on Oct 29, 2021 \| parent \| context \| favorite \| on: Seemingly impossible functional programs (2007) How is not halting O(1)? Wouldn't that be O(∞)?

scapp on Oct 29, 2021 [–]

I think they meant

> Thus if you assume that the function is total and thus does halt, it must run in O(1) time.

Since that's what total means.

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact