Определить точное время выполнения алгоритма по этой нотации нельзя, дает понятие о масштабе сложности, а не о точном его значении.

O(1) - затраты времени не зависят от размера задачи
O(log(n)) - при увеличении размера задачи вдвое, затраты времени меняются на постоянную величину
O(n) - при увеличении размера задачи в 2 раза, затраты времени возрастут тоже в два раза
O(n^2) - при увеличении размера задачи в 2 раза, затраты времени возрастут примерно в четыре раза
O(n*log(n)) - при увеличении задачи в два раза, затраты времени возрастут в два раза, плюс некоторая прибавка, относительный вклад которой уменьшается с ростом n. При малых n может вносить очень большой вклад. O(n*log(n)) начинает расти как квадрат при малых n, но потом рост замедляется почти до линейного
O(n^p) - полиномиальный алгоритмы, остающиеся мечтой для некоторых задач.
O(a^n), O(n!), O(n^n) - неполиномиальные алгоритмы, в порядке ускорения увеличения затрат времени

1)
а) ОС "регистрирует" приложение на серверах APNS\GCM\MPNS и получает Device Token.
б) Приложение получает данный Device Token и должно передать его на ваш сервер (для его дальнейшего использования)
в) Нужно послать Push: используя ранее полученный Device Token передаете своё Push-сообщение на APNS\GCM\MPNS, который в свою очередь отправляет на указанный Device Token ваше Push

Можно использовать еще промежуточный сервис для пероверки актуальности Device Token (так как приложение могло быть переустановлено)

2) appsfire.com
https://www.pushwoosh.com/

3) Не совсем понятно где событие происходит. Если событие на сайте, логично привязывать Dev Token к User'у и тянуть его.

4) Увы не подскажу

onPause
onWindowFocusChanged
вот решение

ну и изучить