Hello everyone! I'm doing a stage 2 Algorithms paper and I've done most of these running time questions. However I'm stuck with doing a proof, and proofs just fly over my head. If someone could please step me through how to do this, I would appreciate it. Also, I'd appreciate being helped more than just given the answer, as that wouldn't really benefit me much :3

At this point, I'm thinking I'd use a proof by contradiction... but... I don't know where to start. I have a similar question which I'm working through at the moment. I'll post it here when I'm done because if that one works out to be correct then I'll feel a lot more confident about this one.

Formally prove that

is not

using the definition of

only.

P.S. I sincerly apologise if I have this in the wrong place. I was unsure of where else to place it.

Thanks in advance for any help!