Linked Questions

194 votes
3 answers
26k views

Is there a system behind the magic of algorithm analysis?

There are lots of questions about how to analyze the running time of algorithms (see, e.g., runtime-analysis and algorithm-analysis). Many are similar, for instance those asking for a cost analysis ...
Raphael's user avatar
  • 72k
101 votes
3 answers
34k views

How does one know which notation of time complexity analysis to use?

In most introductory algorithm classes, notations like $O$ (Big O) and $\Theta$ are introduced, and a student would typically learn to use one of these to find the time complexity. However, there are ...
Jack H's user avatar
  • 1,323
11 votes
2 answers
700 views

How to prove that $n(\log_3(n))^5 = O(n^{1.2})$?

This a homework question from Udi Manber's book. Any hint would be nice :) I must show that: $n(\log_3(n))^5 = O(n^{1.2})$ I tried using Theorem 3.1 of book: $f(n)^c = O(a^{f(n)})$ (for $c >...
Andre Resende's user avatar
8 votes
1 answer
597 views

What counts as an operation?

Apologies for the newbie question, but I am a bit confused about what exactly counts as a "simple operation" when working out the time complexity of an algorithm. In particular, why do we consider all ...
user85798's user avatar
5 votes
2 answers
571 views

BigO, Running Time, Invariants - Learning Resources

What are some good online resources that will help me better understand BigO notation, running time & invariants? I'm looking for lectures, interactive examples if possible.
PancakeOverflow's user avatar
4 votes
2 answers
35k views

Time complexity of a backtrack algorithm

I've developed the following backtrack algorithm, and I'm trying to find out it time complexity. A set of $K$ integers defines a set of modular distances between all pairs of them. In this algorithm, ...
Mahdi Khosravi's user avatar
4 votes
2 answers
717 views

Analysis of algorithms, 'big O' question

The main question is, how exactly is the big O analysis calculated on routines? Is there a specific formula that relates what each function in a program does to a big O calculation? Also, what about ...
user avatar
4 votes
1 answer
1k views

What are elementary operations in time complexity definition?

Wikipedia gives us the following defintion of time complexity: "In computer science, the time complexity is the computational complexity that describes the amount of time it takes to run an ...
Юрій Ярош's user avatar
3 votes
2 answers
15k views

How is the complexity of recursive algorithms calculated and do they admit better complexity than non-recursive algorithms?

How are asymptotical time complexities calculated for recursive algorithms? Recursive algorithms call themselves and therefore take up more space compared to non-recursive algorithms. But are they ...
Shivam Naik's user avatar
3 votes
2 answers
5k views

What is running time of an algorithm?

What do we mean by running time of algorithms? when we say running time of bubble sort is O($n^2$), what are we implying? Is it possible to find the approximate time in minutes/seconds from the ...
bandit_king28's user avatar
3 votes
2 answers
82 views

How to include calls to an $O(n)$ subroutine on finite-sized inputs in an analysis?

I am trying to calculate the runtime complexity of a function that does not have fixed size input, but uses several helper methods that do have fixed size input. I was unsure of how to include the ...
fvrghl's user avatar
  • 141
3 votes
2 answers
6k views

Using software to calculate the complexity of an algorithm

I am somewhat a beginner, and I have often seen complexity being calculated for various algorithms but they never actually gave me a very clear idea about how it is done. Can someone please point some ...
Pankaj Sejwal's user avatar
3 votes
1 answer
2k views

Finding growth of "inter-recursive" functions

consider following code int f(int x) { if(x<1) return 1; else return f(x-1)+g(x); } int g(int x) { if(x<2) return 1; else return f(x-1)+g(x/2); } ...
user1917769's user avatar
3 votes
2 answers
254 views

Determining Big O [duplicate]

i<--2 while (i<n) someWork (...) i <-- power (i,2) done Given that someWork(...) is an O(n) algorithm, what is the worst case ...
user avatar
2 votes
1 answer
56 views

Proving complexity of computing product of matrices

If $A$ is a non-singular $n\times n$ matrix, $B$ is an $n\times p$ matrix, and $C$ is a $p\times n$ matrix (where $1\le p \ll n$), how does one prove that the complexity of $$D=A^{-1}(BC)$$ is $\frac{...
sequence's user avatar
  • 131

15 30 50 per page