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.

Filter by
Sorted by
Tagged with
0
votes
1answer
17 views

Disambiguating Big-O and Theta for Expressing Time Complexity

Can someone please give me an example of two algorithms, one where "Big-O" is the most appropriate expression of how time complexity grows with input size, and one where this would be Θ? Can ...
1
vote
1answer
17 views
1
vote
2answers
67 views

Is $O(\log x) = O(1)$?

A colleague recently brought up this argument when we were talking about big-O runtime analysis and I've been unable to find why it is incorrect: Informally, the argument goes like this: "If the ...
0
votes
1answer
23 views

Find the values for n0 and the constant factor c such that f(n) = n log n is Ω(n)

I was recently introduced to big O and big Omega, as well as big theta. I know that big O is the worse case scenario in terms of runtime, big Omega is the best case scenario, and big theta is in ...
-1
votes
0answers
43 views

find function f where $f \in O(x^{(1+e)})$ where e>0

I've been struggling on this question for a while. find function f where $f(x) \in O(x^{(1+e)})$ is true for every e>0 but for which it is not true that $f(x) \in O(x)$. can anyone give a hint on ...
0
votes
1answer
24 views

Return indices in the two sum problem

Given an array unsorted P of integers and a number m. I am trying to write a code that returns indices ...
0
votes
4answers
88 views

How can I compare two algorithms using their Big-Oh complexities?

I have two recursive algorithms to solve a particular problem. I have calculated their time complexities as $O(n^2\times\log n)$ and $O(n^{2.32})$. I need to find which algorithm is better in terms of ...
0
votes
1answer
30 views

How can we get upper bound in terms of Big Oh notation using Master theorem?

The recursion is: T(n) = 5T(n/2) + O(n) I solved for the time complexity using Master theorem and found Θ(n^2). but, the question has asked to find the upper bound ...
0
votes
1answer
37 views

Is the running time of an algorithm that has O(n^2) where n = 10^5 equal to one that has O(1000000n) where n = 10^ 5?

Hello my question is that if i have two for loops inside each other like this: ...
1
vote
1answer
30 views

What is the Big-O Time Complexity of this code?

I was wondering if someone could please explain what the time complexity is for the code below. I think it would be $O(n)$ because the algorithm will take as much time to execute as there are elements ...
1
vote
1answer
44 views

If f(n) = O(g(n)), g(n) = O(h(n)), is h(n) = Ω(f(n)) true?

I have $f(n) = O(g(n))$ and $g(n) = O(h(n))$. Is $h(n) = \Omega(f(n))$ true, and if so, what constants would make it true? I was thinking that since $f(n) = O(g(n))$ and $g(n) = O(h(n))$ are true, ...
1
vote
0answers
27 views

Does clog(n)-c+1 work for T(n)=T(⌈n/2⌉)+1=O(log(n)) after induction?

The given problem is from CLRS, exercise 4.3-2. Show that the solution of T(n)=T(⌈n/2⌉)+1=O(log(n)) I decided to prove T(n) ≤ clog(n) and this is the result I got:...
0
votes
1answer
30 views

sort is equal to inversions logic

In Bubble sort, the number of swaps/comparisons is equal to the number of inversions. 1st pass it will do (n -1) comparison 2nd pass it will do (n-2) comparison....so on (n-1)n = n^2 - n Worst case ...
0
votes
1answer
27 views

simplified into asymptotic notation

I have a function that needs to be represented in theta form. The below is my answer. But the correct answer is 𝜃(n.2^n) Can someone please explain me how??
0
votes
1answer
31 views

The interpretation of expected time bound for searches in a hash table

As CLRS book,page 260 stated, Thus, the total time required for a successful search is $\Theta{\left(2+\alpha/2-\alpha/2n\right)}=\Theta{(1+\alpha)}$ I wouldn't have any problem if the author says ...
1
vote
2answers
86 views

I want to show, without taking a limit, that $2^\sqrt{2 \log n} \in Ω(\log^2n)$ and $2^\sqrt{2 \log n} \in O(\sqrt{2}^{\log n})$

I want to show, without taking a limit, that $2^\sqrt{2 \log n} \in Ω(\log^2n)$ and $2^\sqrt{2 \log n} \in O(\sqrt{2}^{\log n})$. I will omit what I have tried as it has not been useful.
10
votes
2answers
4k views

Can I multiply Big-O time complexities?

Can I multiply Big-O time complexities? For example: $O(n) \cdot O(n) = O(n^2)$? UPDATE: The question came from my observation that different sources analyze their algorithms in different ways. For ...
2
votes
1answer
61 views

What is the computational complexity in big O notation of an algorithm computing n^n?

I have a number n of size s. What is the computational complexity in big O notation of an algorithm computing n^n? Let's assume I'm using exponentiation by squaring. The result size doubles when we ...
1
vote
2answers
101 views

is it true that if $f(n)\in O(g(n))$ then $f(h(n)) \in O(g(h(n)))$?

is it true that if $f(n)\in O(g(n))$ then $f(h(n)) \in O(g(h(n)))$? I can't figure out how to prove or disprove this. if it is true, is it true only when the function $h$ is invertible?
5
votes
2answers
155 views

How does $Θ(\log(n!))=Θ(\log(n^n)$?

How does $Θ(\log(n!))=Θ(\log(n^n)$? I understand why $Θ(\log(n!))=Θ(n\log(n))$ and $Θ(\log(n^n))=Θ(n\log(n))$, therefore $Θ(\log(n!))=Θ(\log(n^n)$. But I am having trouble reconciling this with the ...
1
vote
2answers
39 views

Does $P=NP$ require an algorithm that uses polynomial space?

if there was an algorithm that runs in polynomial time, but its size requires $O(2^n)$ bits, would that still prove $P=NP$?
0
votes
2answers
82 views

Time Complexity for brute force algorithm finding cliques of size k in a graph, in terms of n m and k

I currently have an algorithm that uses brute force/exhaustive search to find all of the cliques of size exactly k in a graph G. My algorithm is as follows: Generate all subgraphs of size k, and check ...
0
votes
1answer
37 views

Apparently weaker form of big O notation

If instead of saying there exists some $C \in \mathbb{R}^{+}$ and $N \in \mathbb{N}$ such that for any $n \geq N$ we have $f(n) \leq Cg(n)$ we say that there is some $C \in \mathbb{R}^{+}$ and some ...
0
votes
2answers
116 views

Can't understand the $O$ notation for runtime of algorithms

In my book,the $O$-notation is given as: $$O(g)=\{f:\mathbb N\rightarrow \mathbb R_{\geq 0}:\exists \alpha\in \mathbb R_{>0},\exists n_0 \in \mathbb N : \forall n\geq n_0 f(n)\leq \alpha g(n)\}$$ ...
0
votes
0answers
33 views

Which is better $n^3\log n$ or $n^3$ [duplicate]

I am confused between $n^3\log n$ and $n^3$. Normally $n\log n$ is better than $n^3$ but what's about $n^3\log n$
1
vote
1answer
26 views

What does n with an index 0 mean in defenition of Theta/Big Omega/ Big-oh notation?

We define theta notation as follows: $\Theta(g(n))$ = {f(n): there are exist $c_1, c_2$ > 0 and $n_0$ such that 0 $\leq$ $c_1$g(n) $\leq$ f(n) $\leq$ $c_2$g(n) for all n > $n_0$}. I found an ...
-1
votes
1answer
52 views

Why 2^(2n+2) not equal to θ(2^2n)?

I'm trying to prove this expression 2^(2n+2) ≠ θ(2^2n)? Firstly 0 <= c1.2^(2n) <= 2^(2n+2) for this n=1 c1=1 is a solution set. For n = ∞, 0 <= ∞.c1 <= ∞ c1=1 is provide it. So omega ...
0
votes
1answer
24 views

How should I evaluate time complexity for matrix if I have a fixed (constant) amount of rows and columns?

Suppose, that I have a four-by-four matrix and I want to print each element of it. ...
3
votes
2answers
208 views

What would be the big O notation for a function that attempts to find pairs of users that participate in different discussions?

Recently, I started to think of a problem involving the use of Twitter data that would involve finding pairs of users that participate in the most conversations. For example, with each tweet, you get ...
-2
votes
1answer
53 views

Does ⌊1/𝑛⌋∈Θ(1/𝑛) or to Ω(log𝑛)

⌊1/𝑛⌋ - represents the floor function Does the floor or ceiling function affect the complexity under which a function falls? ⌊1/𝑛⌋∈Θ(1/𝑛) or to Ω(log𝑛) Found ...
1
vote
1answer
63 views

Find non common numbers in two arrays

Given two arrays of integers, please write a function that returns all elements present in one of the two arrays but not both. E.g. f([ 1, 3, 5 ], [ 1, 2, 4, 5 ]) -> [ 2, 3, 4 ] I know I can do ...
0
votes
3answers
54 views

Can the worst-case analysis of $f(n)$ be $\Omega(g(n))$ but not $O(g(n))$?

I am struggling to wrap my head around using $\Omega$-notation to describe worst-case running time of an algorithm, or $O$-notation to describe the best-case running time. Specifically, I struggle to ...
0
votes
0answers
42 views

Average depth BST upper bound

I have a question regarding the BST average depth upper bound. Following the proof from Data Strucutures and Algorithms in Java by Weiss (3rd edition), I was wondering if there was some kind of ...
1
vote
1answer
40 views

For a balanced binary search tree what is the worst case case time complexity for accessing all elements within a range of nodes?

I have this question which is asking for the worst case time complexity for a balanced binary search tree, assume the nodes are labeled as integers and we consider a range of ...
0
votes
3answers
89 views

$(\log n)^{\log n}$ lower-bound and upper-bound

we know that $n \geq \log{n}$ however I understand that $(\log n)^{\log n}$ grows faster than $n$. I have been trying to prove this however I can't seem to figure it out.
1
vote
2answers
61 views

Silly question: what counts as a "unit of work" when computing big-Oh time complexity

I am going through a fairly non-rigorous textbook called 'Cracking the code interview' and I am bothered by this terminology called "unit of work". It says in the textbook that certain ...
2
votes
1answer
160 views

Shifted Big Os. How to say O((n+c)!) = O(n!)?

Suppose an algorithm is $O(n!)$, but we need to run it $n$ times, so the total complexity is $nO(n!) = O(n \cdot n!) = O((n+1)! - n!) = O((n+1)!)$ Strictly, there is no constant factor that would make ...
0
votes
1answer
31 views

Is there a function $t$ fulfilling $\mathcal{O}(0) \subset \mathcal{O}(t) \subset \mathcal{O}(1)$?

$f:\mathbb{N} \to \mathbb{N}$ is in $\mathcal{O}(0)$ only if $f(n) \neq 0$ for a finite number of values of $n$. Therefore, $\mathcal{O}(0) \subset \mathcal{O}(1)$ strictly. Is there something in ...
1
vote
1answer
54 views

Big-O notation for Polynomial Time Complexity

Recently we had a quiz where one of the question were - Q: Asymptotic notation for polynomial : - 2^Ο(n) - Ο(n log n) - n^Ο(1) - None of these I know that ...
-3
votes
2answers
82 views

Is $\Omega(n) = O(n \log n)$? [closed]

problem $T(n) = 3T(n/4) + n \log n$ $f(n) = n \log n$ and $g(n) = n$ Why is $\Omega(g(n)) = O(n \log n)$? Is it because $\Omega$ means at some $n$ and constant, $\Omega(g(n)) = O(n \log n)$?
0
votes
2answers
116 views

How to show working for summing of Big O notation

The equation below is intuitively correct, but how do you show that this is actually the case? What is the working out needed? $$\sum_{i=1}^{n-1}O(\lg n)=O(n\lg n)$$
2
votes
3answers
148 views

Finding largest elements

I was asked to find write a pseudocode of an algorithm that extracts the Log(N) largest elements in an array and return them in a sorted list, my attempt is ...
0
votes
2answers
36 views

Trouble with Big-O notation proof by definition

Let $a,b>0$. Prove $\left(\log\left(n\right)\right)^{a}=O\left(n^{b}\right)$. I'm supposed to find an algorithm to find the log(n) largest elements in an array and return them sorted and explain ...
3
votes
3answers
117 views

Is it true that $ 2^{O(3k)} = 2^{O(k)} $?

Is it true that $ 2^{O(3k)} = 2^{O(k)} $? But It should be different from $ O(2^{k}) = 2^{O(k)} $ ? I will be happy for simple explanation. Thanks.
18
votes
3answers
3k views

Time complexity $O(m+n)$ Vs $O(n)$

Consider this algorithm iterating over $2$ arrays $(A$ and $B)$ size of $ A = n$ size of $ B = m$ Please note that $m \leq n$ The algorithm is as follows ...
-1
votes
2answers
48 views

Big-O-notations and Small-o-notations

$a)$ Determine for all pairs $i$ and $j$, $i,j ∈ \{1, \ldots, 6\}$ whether for the ones given below functions $f_i ∈ O(f_j)$ or $f_i ∈ o(f_j)$ or neither of the two applies as $n → \infty$: $f_1 = \...
0
votes
1answer
57 views

Show that $f(n) = O(g(n))$ or $f(n) = \overset{\infty}{\Omega}(g(n))$

Before you downvote, please note that this question is distinct from this similar looking question I came across the following the problem in "The Introduction to Algorithms" by Cormen et. ...
2
votes
2answers
88 views

Big-O notation for lower bound instead of Big-Omega

In the Wikipedia's Binary search tree, one can read Traversal requires $O(n)$ time, since it must visit every node. Since it is question of a lower bound, shouldn't we write Traversal requires $\...
0
votes
1answer
75 views

How does squaring time complexity imply the same time complexity for multiplying different numbers? Isn't it the other way round?

Found this in solutions of a test as being true If you can square an n-bit integer in time $O(n \,log \,n)$, then you can multiply two n-bit integers in time $O(n \, log \,n)$. How does the above ...
2
votes
1answer
18 views

Comparisons of functions, their big-oh and their implications

I don't understand why the $1^{st}$ is false but I think I see why the $2^{nd}$ is true. If $f(n) = O(n^2)$ and $g(n) = O(n^2)$, then $f(n) = O(g(n))$. If $f(n) = O(g(n))$ and $g(n) = O(n^2)$, ...

1
2 3 4 5