This is mad old, but I think I have a good solution that doesn't require any services to run or any special background process.
Simply save the times to persistent memory such as shared preferences. This can be performed at any reference time you need. For me, it's when starting a chronometer so that it can persist even after a reboot. Chronometers relate only to SystemClock.elapsedRealtime(), which is the time since last boot, so you can't use System.currentTimeMillis(), which is the total time since the Unix Epoch (00:00:00 UTC on 1 January 1970).
If you wanted to check if the phone was rebooted only at application start, then add this to your onCreate.
//Create a SharedPreferences
SharedPreferences savedKeys = getApplicationContext().getSharedPreferences("MyPref", 0);
SharedPreferences.Editor editor = savedKeys.edit();
if (((System.currentTimeMillis() - SystemClock.elapsedRealtime())-(savedKeys.getLong("key_oldDelta", 0)))>100) {
//Run code here or set a boolean to true for system reboot.
}
//Save the new values.
editor.putLong("key_oldDelta", (System.currentTimeMillis() - SystemClock.elapsedRealtime()));
editor.commit();
The following part of the code will get the delta (difference) of the current Unix time and system time since last boot:
(System.currentTimeMillis() - SystemClock.elapsedRealtime())
If the system rebooted, those numbers will be larger and smaller respectively compared to what they were before rebooting.
Example: you save times at system time = 100 and Unix time = 1000. You reboot after 450 and restart the app after another 50. 500 has now passed since you recorded the values. They are now 10 and 1500.
New delta: 1500-10=1490
Old delta: 1000-100=900
Delta of deltas: 1490-900=590
The last number will always be higher after a reboot. It doesn't matter how long it's been since the reboot. The difference can only get higher because one number (Unix time) is constantly moving forward and the other is constantly being reset to zero at reboot. My example uses very small numbers to make it easy to understand, but remember the real numbers are in milliseconds, and a fair amount of those have passed since 1970. That's why my code says <100 at the end of the if statement. That gives the app 100 milliseconds to run the math. In reality, it takes more like 1 millisecond, but there's no way a phone will reboot in less than 100, so it's a safe value.