What is Constant Time / O(1) Complexity in DSA?

Рет қаралды 37,035

Greg Hogg

Ай бұрын

FAANG Coding Interviews / Data Structures and Algorithms / Leetcode

Пікірлер: 45

@GregHogg Ай бұрын

Master Data Structures & Algorithms For FREE at AlgoMap.io!

@markusklyver6277 Ай бұрын

This is NOT the definition of O(1). O(1) is the the set of all bounded non-negative functions from N to R.

@Stepbrohelp Ай бұрын

As someone with a mathematical background but who just got into coding, THIS is the explanation I was looking for. I always had a hunch that this must be true, but everywhere I looked, people seemed to just say “constant time is fastest” as if it’s ALWAYS true. It has been driving me MAD to get to the bottom of this. Thank you so much for the confirmation!

@joergsonnenberger6836 Ай бұрын

A good example for why constants matter: the best scaling primality test known is ECPP. It's complexity is O((log n)^5). The problem: the constants are so bad, that the exponential algorithms are faster for most interesting numbers.

@kostya48i57 Ай бұрын

big O notation is not about "coding", it is asymptotic notation, usually used in calculus (for example taylor series). it is strange that you have "math background", but never heard of various notations.

@polycrystallinecandy Ай бұрын

The asymptotic growth notations come from mathematics

@Mystic998 Ай бұрын

Mathematicians don't use asymptotic notation often outside of computer science topics. I've only ever seen it occasionally referenced when dealing with series, and usually not in any rigorous, well-explained way.

@joergsonnenberger6836 Ай бұрын

@@Mystic998 They are used in numerical analysis, but yeah, it's quite easy to study a lot of math without ever being exposed to asymptotic notation.

@nolanrata7537 Ай бұрын

O(1) more accurately means that the time will remain below a constant value even for very large (up to infinity) values of n. The time is still allowed to vary so long as it remains below that upper bound.

@GregHogg Ай бұрын

Yeah true could be under the line as well

@ashwin_mahajan Ай бұрын

I study time and space complexity every time, and every time I forget it

@abebuckingham8198 Ай бұрын

I only write O(∞) algorithms.

@asango_aham Ай бұрын

Chad

@ponmuthu..4796 Ай бұрын

That breakes the definition of algorithm

@markusklyver6277 Ай бұрын

Every algorithm is O(∞).

@abebuckingham8198 Ай бұрын

@@markusklyver6277 That's the joke. 😆

@RS-fz4ps Ай бұрын

The point of big O runtime analysis is for scaling. The goal should be to keep this in mind when writing a solution that could be used, say millions of time consecutively. Your answer may take constant runtime, but if that constant runtime is greater than that of a comparable O(N) you might be missing out. This is why most practical sorting algorithms are hybrids which in the real world.

@dumnor Ай бұрын

There are also considerations with theory vs reality. Sometimes computer architecture or physical limitations can cause runtime coefficients to vary. Memory limitations, graphics cards can do certain operations faster, cache access and registries within CPU. For example linked list vs array, theory says linked list is faster to iterate, but reality is that modern computers 'cheat' the theory by retrieving more data than single byte to the cache. This makes arrays faster to iterate through.

@ashiqurrahman-nu7ik Ай бұрын

Well explained! Good content!

@alchenerd Ай бұрын

What would an O(1/N) task look like? Perhaps filling an N-element array up to a constant length using copies of existing elements in the same array?

@markusklyver6277 Ай бұрын

This is NOT the definition of O(1). O(1) is the the set of all bounded non-negative functions from N to R.

@Nikarus2370 Ай бұрын

IDK what you're on about, this is a video talking about "Big O" in programming, which the OP's description of O(1) is accurate.

@dylanisaac1017 Ай бұрын

@@Nikarus2370no???

@davidespinosa1910 Ай бұрын

@@Nikarus2370 Markus is correct. O(1) means bounded. The function doesn't have to be flat.

@speakoutloud7293 Ай бұрын

Brilliant! Keep going.

@balu5387 Ай бұрын

please make full videos on Time and space complexity

@GregHogg Ай бұрын

Working on it

@davidespinosa1910 Ай бұрын

O(1) doesn't mean flat. It means bounded. Also, for all the big-O notations, it's irrelevant what the program does for small n. So if n is bounded (less than 1 gazillion, for example), then all programs are O(1).

@dhirajsharma5191 Ай бұрын

Can you also explain o(logn) and o(nlogn)

@GregHogg Ай бұрын

I've explained log n about 10 shorts ago, you can check it out

@DreadTeamLeader Ай бұрын

I had a feeling someone would have to talk about speed regarding this.

@Jay_Blvck Ай бұрын

Nice explanation 🔥

@GregHogg Ай бұрын

Thank you!

@dotnet8925 Ай бұрын

Wow

@Sirbikingviking Ай бұрын

So what if you implement a function that uses linear time under a certain input size and switches to hashing over a certain input size

@Nikarus2370 Ай бұрын

Well you'd probably have 2 (or more) dedicated functions to doing the job tuned for the different ranges of N. And then 1 function that checks the input and picks which function should be used.

@808brotherstv4 Ай бұрын

Wow i never thought of it in this perspective

@KaramAlayan Ай бұрын

Thats the importance of expecting the scale of your project for example your website probably wont reach 10 million users so you should only take into account like 100k to be very optimistic here but when a company like google creates a website it should be scalable to numbers far far higher probably for 75% of people on earth