I got a google interview type question from facebook:

You are given an array and an integer k. Find the Kth largest integer in that array.

Expected time complexity - O(n)

Expected space complexity - O(1)

I was shocked by the fact that the time complexity can be O(n) !

Can someone please explain?