Questions tagged [big-o-notation]
Big O Notation is an informal name of the "O(x)" notation used to describe asymptotic behaviour of functions. It is a special case of Landau notation.
65
questions
0
votes
0answers
30 views
Big oh notation run time [duplicate]
I have this Question , I want the answer and show me how to solve it Please :
Analyze the running time of the following algorithm using Big-Oh notation
...
0
votes
0answers
15 views
Growth rate and runtime [duplicate]
Sorry if this maybe a dumb question, just a little confused
But with Big-Oh notation, does it measure the runtime or growth rate of an algo? or both?
0
votes
0answers
17 views
How can I compare by this two algorithms? [duplicate]
I have two algorithms has a complexity of O (n log n) and the B-complex algorithm (n^2). By imposing NA size the larger issue that a algorithm can solve in a given time and NB size the larger issue ...
1
vote
1answer
54 views
why is $O(n^2)$ equal to $n^{1.5}$?
I am learning this MIT course, which gives this formula
$$O(n^2) = n^{1.5}$$
is there a table to calculate this? like $O(n^{1.5})$, $O(n^{5})$ ?
what x takes would have O(x) give $c \cdot n$ where ...
1
vote
2answers
35 views
What does “bounded above” mean in Family of Bachmann–Landau notations?
Per wiki
|f| is bounded above by g (up to constant factor) asymptotically
with this concrete example,
$$f(n) = \log n$$
$$g(n) = n^c = n^{0.000001}$$
Does "bounded above (up to constant factor)...
0
votes
0answers
35 views
how to compute $O(n^{0.000001})$ [duplicate]
this MIT course gives a formula about Big O
$$n^{0.999999} \log n = O(n^{0.999999} \cdot n^{0.000001})$$
going through wiki, i cannot find a similar Big O properties or usages.
how to compute $O(n^{...
2
votes
2answers
2k views
Are “of the order of n” and “Big O” the same thing?
I am learning from the MIT course Introduction to Algorithms.
The professor says:
Now, remember $\Theta(n)$ is essentially something
that says "of the order of $n$".
What does "of the order ...
9
votes
6answers
3k views
Are there variations of the regular runtimes of the Big-O-Notation?
There are multiple $O$-Notations, like $O(n)$ or $O(n^2)$ and so on. I was wondering, if there are variations of those in reality such as $O(2n^2)$ or $O(\log n^2)$, or if those are mathematically ...
1
vote
3answers
91 views
What should I call algorithms with non-linear non-constant time?
I am writing a paper in which I want to refer to a group of algorithms. Some of these algorithms are of complexity O(NlogN), and some of the are more complex (e.g ...
1
vote
1answer
28 views
Comparing different asymptotic notations
Suppose we have 3 algorithms complexity times at the worst case:
A = $O(nlogn)$
B = $O(n\sqrt{n})$
C = $\Theta(n)$
In my opinion, it is not possible to define the best solution, since we don't know ...
7
votes
1answer
423 views
Asymptotics question
Is $\frac {n!} {2!\cdot 4!\cdot 8!\dots (n/2)!}=O(4^n)$?
I am really stuck and I tend to believe it's true, but I don't know how to prove it.
Any help would be appreciated!
2
votes
2answers
332 views
Traveling Salesman Problem: Big O Complexity of Algorithm
I'm trying to figure out how to do this problem in my intro algorithm class, but I'm a little confused.
The Traveling Salesman problem (TSP) is famous. Given a list of
cities and the distances ...
0
votes
3answers
79 views
How can i prove this asymptotic comparison? [duplicate]
This is an exercise that's part of my assignment, but it is optional and flagged as a "challenge". I would like to discuss its solution:
Prove that: $$ 27\log{n} + \sqrt{n} = \theta(\sqrt{n})$$
...
0
votes
2answers
410 views
How to find the big o running time if the recursion function have different cases of recursion with different fraction of n?
How to find the big o running time if the recursion function have different cases of recursion with different fraction of n?
If I have a recursive function like this for example (This is just an ...
0
votes
0answers
34 views
Probability in 1-universal hash function
I am trying to prepare for an exam and I am not sure how to solve this task:
Given is a hash function with m buckets, which uses a 1-universal hash function h: U -> H and handles collisions with ...
