Codility - Lesson 3 Time complexity

Source Link: 
https://codility.com/programmers/lessons/3-time_complexity/ 

Some Notes: 
Use of time complexity makes it easy to estimate the running time of a program.

 3.1: Which is the dominant operation? 
1 def dominant(n): 
2 result = 0 
3 for i in xrange(n): 
4 result += 1 
5 return result

The operation in line 4 is dominant and will be executed n times. The complexity is described in Big-O notation: in this case O(n) — linear complexity.

3.3: Logarithmic time — O(log n).
1 def logarithmic(n):
2 result = 0
3 while n > 1:
4 n //= 2
5 result += 1
6 return result 

The value of n is halved on each iteration of the loop.


3.4. Exercise

Problem: You are given an integer n. Count the total of 1 + 2+. . . + n.

Solution: The task can be solved in several ways. 

The third person’s solution is even quicker.

3.9: Model solution — time complexity O(1).
1 def model_solution(n):
2 result = n * (n + 1) // 2
3 return result

Very Important: 
Sum = (ceiling + floor) * height / 2
(with low time complexity~~~)