Для начала, смотрите комментарий Ларсмана. Логика цикла не обязательно тривиальна для исключения. Допустим, ради аргумента, что вы уверены, что логика цикла не будет нарушена, что логика тривиальна (т.е. нет условных путей, влияющих на выполненную работу), и что вы определяете свою единицу работы, чтобы быть общая логика выполняется за один проход по циклу .
В этом случае ваши верхняя и нижняя границы совпадают. Вы гарантированно выполняете как минимум, и не более, порядка N ^ 2 единиц работы. У вас есть Ω(N^2) и O(N^2). Ваши нижняя и верхняя границы идентичны; Вы можете охарактеризовать Θ(N^2).
Следует еще раз упомянуть, что это бессмысленно, если логика цикла нетривиальна и особенно зависит от того, что вы фактически определяете как единицу работы. Смысл этих обозначений состоит в том, чтобы охарактеризовать ожидаемый объем работы, выполняемый алгоритмом. Вы можете повторять цикл миллионы раз, но это не влияет на эту нотацию, если работа, которую вы действительно заботитесь о том, сколько раз SomeExpensiveFunction() вызывается в этом цикле, и логика диктует, что она вызывается только один раз.