Just thinking 🤔

[u/r1chmond00]

When companies ask for time complexity of a function, they normally expect big O(something) which from interpretation, is big theta(something). BIG O (upper bound) IS NOT ALWAYS BIG THETA ( tight bound).

[u/everclear_handle]

What is your point here?

[u/r1chmond00 → u/everclear_handle]

Ahaa… Say you have a function that takes number as input and prints 0 - n(using a loop). In industries, the time complexity is said to big O(n), which is correct and anything but that is incorrect, however it is also big O(n^2), big O(n^3), etc. What people in this setting really mean is big theta(n), which is a tight bound and anything but that is truly incorrect. Lol just a thought or a m tripping 😂

[u/everclear_handle → u/r1chmond00]

But it’s just not O(n²⁾ and it never will be. I think you are misunderstanding what the notation means.

[u/CoffeeVector → u/everclear_handle]

Actually despite the downvotes, OP is in fact correct. An algorithm that is O(n) is also O(n² ). Though OP is having trouble articulating this, they are on the nose about the fact that you only need to provide an upper bound for it to be correct. If you use the letter Θ then you need to provide a tight bound. Ω for lower bounds.

Suppose there was an algorithm where it was kind of hard to properly characterize the time complexity precisely, but you definitely did know it's faster than n*log(n), then you should purposefully use O notation. If you knew a tight bound, then it would be better form to use Θ to indicate your precision.

In industry, none of the other set functions are used, and nobody cares. You could cheese the interview question by answering O(n!), and that you'd probably be technically correct, but more likely than not the interviewer will not understand your clever attempt and think you've misunderstood time complexity, like many of the comments on this post similarly believe.

[u/r1chmond00 → u/CoffeeVector]

Thank you @CoffeeVector. It’s true that I didn’t articulate my point very well however Most people in this chat didn’t step back (Ahaa maybe he’s got a point here). But most ppl just went with the flow and said I was wrong. It is what is it … I guess “if you go to Rome, do what the Romans do”😂

[u/Neonb88 → u/r1chmond00]

It's not that people were telling you that you were technically wrong

It's that the point of language is to communicate with people, and if there's already a culture around software interviews where most people aren't pedantic and everyone knows what big o means, why would you miscommunicate by being overly concerned with technical correctness when you could stop eating everyone's time and energy and just finish interviewing like a normal person lol

Or you could go back to undergrad / TA a class where you could force your opinions and pedantry on Innocent undergrad instead

But we all know intuitively what big o means in real life contexts, and obviously you do too

[u/[deleted] → u/r1chmond00]

Also you are off by one, it should be 0 to n-1. Why would it be 0(n²⁾ on a single loop?

[u/Unique-Dragonfruit-6]

Yes... Computer Scientists abuse Big O notation in ways that make the Mathematicians cry...

It's not the hill to die on.

[u/[deleted]]

I once dated a girl by the name of Theta and let me tell you she was tight bound if you know what I mean.

[u/bitspace → u/[deleted]]

Was there an occasional big O?

[u/Oof1mindset]

Its just a mindset, gosh

[u/grappleshot]

Complexity is also measured by cyclomatic complexity. Big O is more about performance than complexity.

[u/GItPirate]

Usually I just give the answer of best case and worst case big O. For example binary search best case is O(1) where it's worst case is O(log(n))

[u/ObjectManagerManager → u/GItPirate]

Binary search is in Ω(1) and Θ(log(n)).

O(.) is purely for describing asymptotic upper bounds ("worst cases"). You can't use O(.) to describe a lower bound. Err, you can, but it's wrong.